W Code - Pattern-Based DSA Learning Platform

Bhanu Bisht

Back to DSA Theory

Advanced Graph Algorithms

Shortest paths, MSTs, and network connectivity algorithms.

Topics

Minutes

O(E log V)

Dijkstra

Visualizer

Dijkstra's Algorithm

O(E log V)

Interactive

Loading visualizer...

Single-Source Shortest Paths (Non-Negative Weights)

Imagine routing water pipes or electrical cables. To find the shortest path from a main distribution valve (source) to all houses, you always expand the water line from the valve that has the shortest filled pipeline first (using a min-heap), and then update the pressure bounds (relaxation) to its immediate adjacent pipeline branches.

Dijkstra's Algorithm is a greedy algorithm designed to find the shortest path from a single source node to all other nodes in a weighted graph with non-negative weights.

Algorithm Steps:

Initialize distances: Set the distance of the source node to 0 and all other nodes to infinity (∞).
Utilize a Min-Heap (Priority Queue) to always extract the unvisited node u with the smallest calculated distance.
Relax Neighbors: For each adjacent node v, check if routing through u yields a shorter path: if (dist[u] + weight(u, v) < dist[v]) { dist[v] = dist[u] + weight(u, v) }
Push the updated distance and neighbor back into the priority queue. Repeat until all reachable nodes are processed.

Why Priority Queue (Min-Heap)?

Using a min-heap allows us to query the next closest node in O(log V) time, which is highly efficient.

C++ Code — Dijkstra's Algorithm

vector<int> dijkstra(int V, vector<vector<pair<int,int>>>& adj, int src) {
    priority_queue<pair<int,int>, vector<pair<int,int>>, greater<pair<int,int>>> pq;
    vector<int> dist(V, 1e9);

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

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

        if (d > dist[u]) continue; 

        for(auto it : adj[u]) {
            int v = it.first;
            int weight = it.second;
            if (dist[u] + weight < dist[v]) {
                dist[v] = dist[u] + weight;
                pq.push({dist[v], v});
            }
        }
    }
    return dist;
}

Bellman-Ford Algorithm

O(V * E)

Shortest Paths with Negative Weights

Think of currency arbitrage. In forex, trading across multiple currencies can create cycles where you end up with more money than you started (negative cycles). Dijkstra can get stuck in infinite loops here, so Bellman-Ford systematically recalculates all paths V - 1 times and does a final run to detect these loops.

The Bellman-Ford Algorithm computes single-source shortest paths on weighted graphs and, unlike Dijkstra, supports edges with negative weights and detects negative cycles.

Key Mechanisms:

Edge Relaxation: Systematically relaxes all edges in the graph exactly V - 1 times (where V is the number of vertices).
Negative Cycle Detection: Performs a final relaxation check on all edges. If any distance is still reduced, a negative weight cycle exists in the graph, meaning an infinitely negative path can be formed.

Comparison:

Dijkstra: Faster, but fails if negative weight edges exist.
Bellman-Ford: Slower, but robust enough to handle negative weights and detect circular negative weight cycles.

C++ Code — Bellman-Ford Algorithm

vector<int> bellmanFord(int V, vector<vector<int>>& edges, int src) {
    vector<int> dist(V, 1e9);
    dist[src] = 0;

    // Relax all edges V-1 times
    for (int i = 0; i < V - 1; i++) {
        for (auto it : edges) {
            int u = it[0], v = it[1], wt = it[2];
            if (dist[u] != 1e9 && dist[u] + wt < dist[v]) {
                dist[v] = dist[u] + wt;
            }
        }
    }

    // Check for Negative Cycle
    for (auto it : edges) {
        int u = it[0], v = it[1], wt = it[2];
        if (dist[u] != 1e9 && dist[u] + wt < dist[v])
            return {-1}; // Cycle Detected
    }
    return dist;
}

Floyd-Warshall Algorithm

O(V³)

All-Pairs Shortest Paths

Think of a flight connection system like a giant hub. To calculate the flight time between any two cities, you try inserting an intermediate airport (like London, Dubai, or Tokyo) to see if routing through it reduces the total flight time.

The Floyd-Warshall Algorithm is a dynamic programming algorithm that finds the shortest paths between all pairs of vertices.

Dynamic Programming Formulation:

For every pair of vertices (i, j), check if routing through an intermediate vertex k yields a shorter path: dist[i][j] = min(dist[i][j], dist[i][k] + dist[k][j])

Practical Use:

Best suited for finding all-pairs shortest paths in small-to-medium graphs (typically V <= 400) because of its cubic time complexity.

C++ Code — Floyd-Warshall Algorithm

void floydWarshall(vector<vector<int>>& matrix) {
    int n = matrix.size();
    
    for (int k = 0; k < n; k++) {
        for (int i = 0; i < n; i++) {
            for (int j = 0; j < n; j++) {
                if (matrix[i][k] == -1 || matrix[k][j] == -1) continue;
                
                // If direct path is absent or longer than path via k
                if (matrix[i][j] == -1 || matrix[i][j] > matrix[i][k] + matrix[k][j]) {
                    matrix[i][j] = matrix[i][k] + matrix[k][j];
                }
            }
        }
    }
}

Disjoint Set Union (DSU)

O(4α) ≈ O(1)

Partitioned Equivalence Sets

Think of joining kingdoms. Each kingdom has a king (representative parent). When two kingdoms merge (Union), the smaller kingdom swears allegiance to the king of the larger kingdom (Union by rank), and when someone asks who is their ruler (Find), they walk straight to the top king and remember his name for future queries (Path Compression).

The Disjoint Set Union (DSU) (or Union-Find) data structure maintains partition collections of elements grouped into non-overlapping subsets.

Two Essential Operations:

Find: Determines which subset a particular element belongs to, returning its representative parent node.
Union: Merges two separate subsets into a single joint subset.

Core Optimization Techniques:

Path Compression: Simplifies the tree structure during Find operations by pointing visited nodes directly to the root parent, speeding up future lookups.
Union by Rank/Size: Attaches the shallower tree to the root of the deeper tree during Union operations to keep the tree height small.
Time Complexity: Combining both optimizations makes DSU operations run in nearly O(1) time (modeled by the Inverse Ackermann function α).

C++ Code — Disjoint Set Union (DSU)

class DSU {
    vector<int> parent, rank;
public:
    DSU(int n) {
        parent.resize(n + 1);
        rank.resize(n + 1, 0);
        for(int i = 0; i <= n; i++) parent[i] = i;
    }

    int findUPar(int node) {
        if(node == parent[node]) return node;
        return parent[node] = findUPar(parent[node]); // Path Compression
    }

    void unionByRank(int u, int v) {
        int ulp_u = findUPar(u);
        int ulp_v = findUPar(v);
        if(ulp_u == ulp_v) return;
        
        if(rank[ulp_u] < rank[ulp_v]) {
            parent[ulp_u] = ulp_v;
        } else if(rank[ulp_v] < rank[ulp_u]) {
            parent[ulp_v] = ulp_u;
        } else {
            parent[ulp_v] = ulp_u;
            rank[ulp_u]++;
        }
    }
};

MST: Kruskal's Algorithm

O(E log E)

Edge-Based Spanning Trees

Imagine laying fiber-optic cables between cities to connect them with the lowest total cable cost. To do this, you write down the costs of all possible lines, sort them from cheapest to most expensive, and lay cables one-by-one, skipping any line that would connect cities already in the same network (using DSU to check cycles).

Kruskal's Algorithm is a greedy algorithm used to find the Minimum Spanning Tree (MST) of a connected, undirected graph.

Algorithm Steps:

Collect all edges in the graph and sort them in non-decreasing order of their weights.
Initialize a DSU structure containing all vertices as separate sets.
Iterate through the sorted edges: if the vertices of the current edge belong to different sets, add the edge to the MST and merge their sets using Union. If they are in the same set, discard the edge to prevent a cycle.
Repeat until the MST contains V - 1 edges.

C++ Code — MST: Kruskal's Algorithm

int spanningTree(int V, vector<vector<int>> adj[]) {
    vector<pair<int, pair<int, int>>> edges;
    for (int i = 0; i < V; i++) {
        for (auto it : adj[i]) {
            int adjNode = it[0];
            int wt = it[1];
            int node = i;
            edges.push_back({wt, {node, adjNode}});
        }
    }
    
    sort(edges.begin(), edges.end());
    DSU ds(V);
    int mstWt = 0;
    
    for (auto it : edges) {
        int wt = it.first;
        int u = it.second.first;
        int v = it.second.second;

        if (ds.findUPar(u) != ds.findUPar(v)) {
            mstWt += wt;
            ds.unionByRank(u, v);
        }
    }
    return mstWt;
}

MST: Prim's Algorithm

O(E log V)

Node-Based Spanning Trees

Imagine growing a crystal. You start at one seed atom (arbitrary node) and greedily attach the closest adjacent atom available, growing the structure outward until all atoms are connected.

Prim's Algorithm is a node-based greedy algorithm that grows the Minimum Spanning Tree (MST) one vertex at a time.

Algorithm Steps:

Start with a single arbitrary node and mark it as visited.
Maintain a Min-Heap (Priority Queue) to store edges pointing to unvisited nodes, sorted by weight.
Extract the minimum-weight edge from the priority queue. If the destination vertex is already visited, discard it; otherwise, add the edge to the MST and mark the vertex as visited.
Add all edges originating from this newly visited vertex to the priority queue. Repeat until all vertices are visited.

Kruskal vs Prim:

Prim's Algorithm: Performs better on dense graphs (where the number of edges E is close to V²).
Kruskal's Algorithm: Performs better on sparse graphs since it sorts edges directly and uses a simple DSU structure.

C++ Code — MST: Prim's Algorithm

int spanningTree(int V, vector<vector<int>> adj[]) {
    priority_queue<pair<int, int>, vector<pair<int, int>>, greater<pair<int, int>>> pq;
    vector<int> vis(V, 0);
    
    // {weight, node}
    pq.push({0, 0}); 
    int sum = 0;

    while (!pq.empty()) {
        auto it = pq.top();
        pq.pop();
        int wt = it.first;
        int node = it.second;

        if (vis[node]) continue;
        vis[node] = 1;
        sum += wt;

        for (auto it : adj[node]) {
            int adjNode = it[0];
            int edW = it[1];
            if (!vis[adjNode]) {
                pq.push({edW, adjNode});
            }
        }
    }
    return sum;
}

Single-Source Shortest Paths (Non-Negative Weights)

Dijkstra's Algorithm is a greedy algorithm designed to find the shortest path from a single source node to all other nodes in a weighted graph with non-negative weights.

Algorithm Steps:

Initialize distances: Set the distance of the source node to 0 and all other nodes to infinity (∞).
Utilize a Min-Heap (Priority Queue) to always extract the unvisited node u with the smallest calculated distance.
Relax Neighbors: For each adjacent node v, check if routing through u yields a shorter path: if (dist[u] + weight(u, v) < dist[v]) { dist[v] = dist[u] + weight(u, v) }
Push the updated distance and neighbor back into the priority queue. Repeat until all reachable nodes are processed.

Why Priority Queue (Min-Heap)?

Using a min-heap allows us to query the next closest node in O(log V) time, which is highly efficient.

vector<int> dijkstra(int V, vector<vector<pair<int,int>>>& adj, int src) { priority_queue<pair<int,int>, vector<pair<int,int>>, greater<pair<int,int>>> pq; vector<int> dist(V, 1e9); dist[src] = 0; pq.push({0, src}); while(!pq.empty()) { int d = pq.top().first; int u = pq.top().second; pq.pop(); if (d > dist[u]) continue; for(auto it : adj[u]) { int v = it.first; int weight = it.second; if (dist[u] + weight < dist[v]) { dist[v] = dist[u] + weight; pq.push({dist[v], v}); } } } return dist; }

vector<int> bellmanFord(int V, vector<vector<int>>& edges, int src) { vector<int> dist(V, 1e9); dist[src] = 0; // Relax all edges V-1 times for (int i = 0; i < V - 1; i++) { for (auto it : edges) { int u = it[0], v = it[1], wt = it[2]; if (dist[u] != 1e9 && dist[u] + wt < dist[v]) { dist[v] = dist[u] + wt; } } } // Check for Negative Cycle for (auto it : edges) { int u = it[0], v = it[1], wt = it[2]; if (dist[u] != 1e9 && dist[u] + wt < dist[v]) return {-1}; // Cycle Detected } return dist; }

void floydWarshall(vector<vector<int>>& matrix) { int n = matrix.size(); for (int k = 0; k < n; k++) { for (int i = 0; i < n; i++) { for (int j = 0; j < n; j++) { if (matrix[i][k] == -1 || matrix[k][j] == -1) continue; // If direct path is absent or longer than path via k if (matrix[i][j] == -1 || matrix[i][j] > matrix[i][k] + matrix[k][j]) { matrix[i][j] = matrix[i][k] + matrix[k][j]; } } } } }

class DSU { vector<int> parent, rank; public: DSU(int n) { parent.resize(n + 1); rank.resize(n + 1, 0); for(int i = 0; i <= n; i++) parent[i] = i; } int findUPar(int node) { if(node == parent[node]) return node; return parent[node] = findUPar(parent[node]); // Path Compression } void unionByRank(int u, int v) { int ulp_u = findUPar(u); int ulp_v = findUPar(v); if(ulp_u == ulp_v) return; if(rank[ulp_u] < rank[ulp_v]) { parent[ulp_u] = ulp_v; } else if(rank[ulp_v] < rank[ulp_u]) { parent[ulp_v] = ulp_u; } else { parent[ulp_v] = ulp_u; rank[ulp_u]++; } } };

int spanningTree(int V, vector<vector<int>> adj[]) { vector<pair<int, pair<int, int>>> edges; for (int i = 0; i < V; i++) { for (auto it : adj[i]) { int adjNode = it[0]; int wt = it[1]; int node = i; edges.push_back({wt, {node, adjNode}}); } } sort(edges.begin(), edges.end()); DSU ds(V); int mstWt = 0; for (auto it : edges) { int wt = it.first; int u = it.second.first; int v = it.second.second; if (ds.findUPar(u) != ds.findUPar(v)) { mstWt += wt; ds.unionByRank(u, v); } } return mstWt; }

int spanningTree(int V, vector<vector<int>> adj[]) { priority_queue<pair<int, int>, vector<pair<int, int>>, greater<pair<int, int>>> pq; vector<int> vis(V, 0); // {weight, node} pq.push({0, 0}); int sum = 0; while (!pq.empty()) { auto it = pq.top(); pq.pop(); int wt = it.first; int node = it.second; if (vis[node]) continue; vis[node] = 1; sum += wt; for (auto it : adj[node]) { int adjNode = it[0]; int edW = it[1]; if (!vis[adjNode]) { pq.push({edW, adjNode}); } } } return sum; }