Data Structures and Algorithms in C (DSA)

📘 Chapter: Shortest Path Algorithms (Dijkstra, Bellman-Ford)

The Shortest Path Problem is one of the most fundamental and widely studied problems in graph theory. Given a graph with vertices and edges (often with associated "weights" or "costs"), the goal is to find a path between two specified vertices (or from a source to all other vertices) such that the sum of the weights of its constituent edges is minimized. This problem has countless real-world applications, from GPS navigation to network routing.

🛣️ Types of Shortest Path Problems

• Single-Source Shortest Path (SSSP): Find the shortest paths from a single source vertex to all other vertices in the graph. (Dijkstra, Bellman-Ford)
• Single-Pair Shortest Path: Find the shortest path between a specific pair of vertices. (Can be solved by SSSP algorithms, stopping when target is found).
• All-Pairs Shortest Path (APSP): Find the shortest paths between all possible pairs of vertices. (Floyd-Warshall, discussed later).

For unweighted graphs, BFS naturally finds the shortest path (in terms of number of edges). However, for weighted graphs, we need more sophisticated algorithms.

🚀 1. Dijkstra's Algorithm

Dijkstra's Algorithm is a greedy algorithm that finds the shortest paths from a single source vertex to all other vertices in a graph with non-negative edge weights. It works by iteratively building a set of vertices for which the shortest path from the source has been finalized. It's similar in spirit to BFS, but it uses a **Min-Priority Queue** to efficiently select the next vertex to process.

Dijkstra's Algorithm Steps:

1. Initialize `dist[v] = infinity` for all vertices `v`, and `dist[source] = 0`.
2. Create a min-priority queue and insert `(0, source)` (distance, vertex).
3. While the priority queue is not empty:
   • Extract the vertex `u` with the smallest `dist[u]` from the priority queue.
   • If `u` has already been finalized (or if the extracted distance is greater than the already known shortest distance to `u` in case of duplicate entries in PQ), continue.
   • For each neighbor `v` of `u` connected by an edge `(u, v)` with weight `w`:
     • Relaxation Step: If `dist[u] + w < dist[v]`:
       • Update `dist[v] = dist[u] + w`.
       • Insert/update `(dist[v], v)` in the priority queue.

// Conceptual C++ for Dijkstra's Algorithm using std::priority_queue
// Adjacency list: vector> adj[V]; // {neighbor, weight}

void dijkstra(int source, int V, const vector<vector<pair<int, int>>>& adj) {
    vector<int> dist(V, INT_MAX); // Stores shortest distance from source
    priority_queue<pair<int, int>, vector<pair<int, int>>, greater<pair<int, int>>> pq; // {distance, vertex}

    dist[source] = 0;
    pq.push({0, source});

    while (!pq.empty()) {
        int d = pq.top().first;
        int u = pq.top().second;
        pq.pop();

        // If we found a shorter path to u already, skip this one
        if (d > dist[u]) continue;

        // Explore neighbors
        for (auto& edge : adj[u]) {
            int v = edge.first;
            int weight = edge.second;

            // Relaxation step
            if (dist[u] != INT_MAX && dist[u] + weight < dist[v]) {
                dist[v] = dist[u] + weight;
                pq.push({dist[v], v});
            }
        }
    }

    cout << "Shortest distances from source " << source << ":" << endl;
    for (int i = 0; i < V; ++i) {
        cout << "Node " << i << ": " << (dist[i] == INT_MAX ? "INF" : to_string(dist[i])) << endl;
    }
}
  

Dijkstra's Time & Space Complexity:

• Time: $O(E \log V)$ or $O(E + V \log V)$ with a Fibonacci heap. With `std::priority_queue` (binary heap), it's typically $O(E \log V)$ because each of $E$ edge relaxations might lead to a `log V` operation on the heap.
• Space: $O(V + E)$ for adjacency list and distance array/priority queue.

Limitation: Dijkstra's algorithm does NOT work correctly with negative edge weights because its greedy nature assumes that once a node's distance is finalized, it won't be improved by a path going through a later-discovered negative edge.

📉 2. Bellman-Ford Algorithm

The Bellman-Ford Algorithm solves the single-source shortest path problem for graphs that can have negative edge weights. Unlike Dijkstra, it's not greedy. Instead, it repeatedly relaxes all edges in the graph $V-1$ times.

Bellman-Ford Algorithm Steps:

1. Initialize `dist[v] = infinity` for all vertices `v`, and `dist[source] = 0`.
2. Repeat $V-1$ times:
   • For each edge `(u, v)` with weight `w` in the graph:
     • Relaxation Step: If `dist[u] + w < dist[v]`:
       • `dist[v] = dist[u] + w`.
3. Negative Cycle Detection: After $V-1$ iterations, run one more iteration over all edges. If any `dist[v]` can still be decreased, it means there's a negative cycle reachable from the source. Shortest paths are undefined in the presence of negative cycles (they can become infinitely small).

// Conceptual C++ for Bellman-Ford Algorithm
// Edges stored as a list of tuples: vector> edges; // {u, v, weight}

void bellman_ford(int source, int V, const vector<tuple<int, int, int>>& edges) {
    vector<int> dist(V, INT_MAX);
    dist[source] = 0;

    // Relax all edges V-1 times
    for (int i = 0; i < V - 1; ++i) {
        for (const auto& edge : edges) {
            int u = get<0>(edge);
            int v = get<1>(edge);
            int weight = get<2>(edge);

            if (dist[u] != INT_MAX && dist[u] + weight < dist[v]) {
                dist[v] = dist[u] + weight;
            }
        }
    }

    // Check for negative cycles
    bool has_negative_cycle = false;
    for (const auto& edge : edges) {
        int u = get<0>(edge);
        int v = get<1>(edge);
        int weight = get<2>(edge);

        if (dist[u] != INT_MAX && dist[u] + weight < dist[v]) {
            has_negative_cycle = true;
            break;
        }
    }

    if (has_negative_cycle) {
        cout << "Graph contains a negative cycle reachable from source " << source << "!" << endl;
    } else {
        cout << "Shortest distances from source " << source << ":" << endl;
        for (int i = 0; i < V; ++i) {
            cout << "Node " << i << ": " << (dist[i] == INT_MAX ? "INF" : to_string(dist[i])) << endl;
        }
    }
}
  

Bellman-Ford Time & Space Complexity:

• Time: $O(V \cdot E)$ because it iterates $V-1$ times, and in each iteration, it processes all $E$ edges.
• Space: $O(V)$ for the distance array.

Advantages: Can handle negative edge weights, detects negative cycles.
Disadvantages: Slower than Dijkstra for graphs with only non-negative weights.

⚖️ Dijkstra vs. Bellman-Ford: A Comparison

For all-pairs shortest paths, the Floyd-Warshall algorithm (dynamic programming) or running SSSP algorithms from each vertex are used.

📌 Real-Life Example (UdaanPath)

Shortest path algorithms are critical for optimizing routes, resource allocation, and connectivity in many systems, including educational platforms:

• Learning Path Optimization (Dijkstra): Imagine a skill graph where nodes are skills and edge weights are the "effort" or "time" required to transition between related skills. Dijkstra's could find the least-effort path for a user to acquire a target skill from their current set of skills.
• Content Delivery Network (CDN) Optimization (Dijkstra): While complex, at a high level, CDNs use shortest path concepts to find the fastest route to deliver content (videos, images) from servers to users, minimizing latency. Here, weights could represent network latency or traffic.
• Task Dependencies with Costs (Bellman-Ford): If you model tasks as nodes and dependencies as edges, with associated "cost" or "time" (which could potentially be negative if a task speeds up others under certain conditions), Bellman-Ford could find the minimum total cost to complete a set of tasks. It could also detect if a set of dependencies creates an "arbitrage" opportunity (a negative cycle) where endless "value" is generated.
• Internal API Routing/Microservices (Dijkstra): In a large microservices architecture, if an API call needs to chain through multiple services, and each inter-service call has an associated latency (weight), Dijkstra could determine the fastest path for a request to fulfill its goal.

✅ Summary: Finding the Optimal Route

• The Shortest Path Problem aims to find the path with minimum total weight between vertices.
• Dijkstra's Algorithm:
  • Uses a greedy approach and a min-priority queue.
  • Works only with non-negative edge weights.
  • Time: $O(E \log V)$. Space: $O(V+E)$.
• Bellman-Ford Algorithm:
  • Repeatedly relaxes all edges $V-1$ times.
  • Handles negative edge weights and detects negative cycles.
  • Time: $O(V \cdot E)$. Space: $O(V)$.
• Choose Dijkstra for non-negative weights (faster), Bellman-Ford for negative weights or cycle detection.

📤 Coming Next: Minimum Spanning Tree (Kruskal, Prim)

From finding the shortest path between points, we now shift our focus to connecting all points with minimum cost. Our next chapter will introduce Minimum Spanning Trees (MSTs) and explore two classical algorithms for finding them: Kruskal's Algorithm and Prim's Algorithm. This is crucial for network design and optimization problems.