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...

Dijkstra's Algorithm finds the shortest path from a starting node to all other nodes in a graph with non-negative weights.

How it works (Greedy):
1. Set distance to source = 0, others = ∞.
2. Use a Priority Queue (Min-Heap) to pick the unvisited node with the smallest distance.
3. Relax neighbors: If dist[u] + weight < dist[v], update dist[v].
4. Iterate until all reachable nodes are processed.

Why Min-Heap? To always get the closest node efficiently in O(log V).

C++ Code

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)

Bellman-Ford is used for shortest paths when edges can have negative weights.

Comparison:
- Dijkstra: Faster, but fails with negative weights.
- Bellman-Ford: Slower, but handles negative weights and detects negative cycles.

Steps:
1. Relax all edges V-1 times.
2. Try relaxing one more time. If any distance reduces, a Negative Cycle exists!

C++ Code

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³)

Floyd-Warshall computes shortest paths between ALL pairs of vertices.

Core Logic:
It uses Dynamic Programming. For every pair (i, j), it checks if going through an intermediate node k is shorter.
dist[i][j] = min(dist[i][j], dist[i][k] + dist[k][j])

Usage:
Best for small graphs (V < 500) where you need distances between every pair.

C++ Code

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)

DSU (Union-Find) efficiently tracks partitioned sets. It supports:
1. Find(x): Which set does x belong to?
2. Union(x, y): Merge sets of x and y.

Optimizations:
- Path Compression: Flattens tree structure during Find.
- Union by Rank/Size: Attaches smaller tree to larger tree.

With both, operations are nearly O(1) (specifically Inverse Ackermann).

C++ Code

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)

Minimum Spanning Tree (MST): A subset of edges that connects all vertices with minimum total weight and no cycles.

Kruskal's Approach:
1. Sort all edges by weight.
2. Iterate through edges and add them if they don't form a cycle.
3. Use DSU to check for cycles efficiently.

C++ Code

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)

Prim's Algorithm also finds the MST but uses a "greedy node" approach similar to Dijkstra.

How it works:
1. Start from an arbitrary node (e.g., node 0).
2. Use a Priority Queue to store edges (weight, node, parent) originating from the visited set.
3. Always pick the minimum weight edge that connects to an unvisited node.
4. Add it to the MST and mark the new node as visited.

Prim vs Kruskal:
- Prim is faster for Dense Graphs (lots of edges).
- Kruskal is faster/simpler for Sparse Graphs.

C++ Code

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;
}

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; }