Chapter 13: Graph Algorithms (Dijkstra, Bellman-Ford, Prim's, Kruskal's)

Introduction

Weighted graphs model real-world scenarios where edges have costs—distances, times, prices, or capacities. This chapter covers classic algorithms for finding shortest paths and minimum spanning trees. These algorithms power GPS navigation, network routing, resource optimization, and countless other applications.

Why This Matters

Graph algorithms solve optimization problems:

GPS Navigation: Fastest route between locations (Dijkstra)
Network Routing: Optimal packet delivery (Bellman-Ford)
Infrastructure Planning: Minimum cost to connect cities (Prim's, Kruskal's)
Telecommunications: Laying cable with minimum cost
Circuit design: Connecting components efficiently
Logistics: Route optimization for delivery

How to Study This Chapter

Understand problem definitions - Shortest path vs minimum spanning tree
Trace algorithms by hand - Work through examples step by step
Compare algorithms - When to use which algorithm
Implement all variants - Different data structures, optimizations
Analyze complexity - Understand performance trade-offs

Shortest Path Algorithms

Problem Definition

Single-source shortest path: Find shortest paths from one source vertex to all other vertices in a weighted graph.

Dijkstra's Algorithm

Dijkstra's algorithm finds shortest paths from a source to all vertices in graphs with non-negative edge weights. Uses a greedy approach with a priority queue.

Algorithm

1. Initialize:
   - distance[source] = 0
   - distance[all others] = ∞
   - Create min-heap with all vertices (key = distance)

2. While heap is not empty:
   a. Extract vertex u with minimum distance
   b. For each neighbor v of u:
      - If distance[u] + weight(u, v) < distance[v]:
        * distance[v] = distance[u] + weight(u, v)
        * parent[v] = u
        * Update v's key in heap

Visualization

Graph:
    0 --4-- 1 --1-- 3
    |       |       |
    2       6       2
    |       |       |
    2 --3-- 4 --5-- 5

Finding shortest paths from 0:

Initial: dist = [0, ∞, ∞, ∞, ∞, ∞]

Step 1: Process 0
  Update 1: dist[1] = 4
  Update 2: dist[2] = 2
  dist = [0, 4, 2, ∞, ∞, ∞]

Step 2: Process 2 (min = 2)
  Update 4: dist[4] = 5
  dist = [0, 4, 2, ∞, 5, ∞]

Step 3: Process 1 (min = 4)
  Update 3: dist[3] = 5
  Update 4: dist[4] = min(5, 10) = 5
  dist = [0, 4, 2, 5, 5, ∞]

Step 4: Process 4 (min = 5)
  Update 5: dist[5] = 10
  dist = [0, 4, 2, 5, 5, 10]

Final distances from 0:
  0→0: 0
  0→1: 4
  0→2: 2
  0→3: 5
  0→4: 5
  0→5: 10

C Implementation

#include <stdio.h>
#include <stdlib.h>
#include <limits.h>
#include <stdbool.h>

#define MAX_VERTICES 100
#define INF INT_MAX

typedef struct {
    int vertex;
    int weight;
} Edge;

typedef struct {
    Edge edges[MAX_VERTICES];
    int size;
} MinHeap;

int parent(int i) { return (i - 1) / 2; }
int leftChild(int i) { return 2 * i + 1; }
int rightChild(int i) { return 2 * i + 2; }

void swap(Edge* a, Edge* b) {
    Edge temp = *a;
    *a = *b;
    *b = temp;
}

void minHeapify(MinHeap* heap, int i) {
    int smallest = i;
    int left = leftChild(i);
    int right = rightChild(i);

    if (left < heap->size && heap->edges[left].weight < heap->edges[smallest].weight) {
        smallest = left;
    }

    if (right < heap->size && heap->edges[right].weight < heap->edges[smallest].weight) {
        smallest = right;
    }

    if (smallest != i) {
        swap(&heap->edges[i], &heap->edges[smallest]);
        minHeapify(heap, smallest);
    }
}

Edge extractMin(MinHeap* heap) {
    Edge minEdge = heap->edges[0];
    heap->edges[0] = heap->edges[heap->size - 1];
    heap->size--;
    minHeapify(heap, 0);
    return minEdge;
}

void dijkstra(int graph[MAX_VERTICES][MAX_VERTICES], int numVertices, int source) {
    int dist[MAX_VERTICES];
    bool visited[MAX_VERTICES];

    for (int i = 0; i < numVertices; i++) {
        dist[i] = INF;
        visited[i] = false;
    }

    dist[source] = 0;

    for (int count = 0; count < numVertices - 1; count++) {
        // Find minimum distance vertex
        int minDist = INF;
        int u = -1;

        for (int v = 0; v < numVertices; v++) {
            if (!visited[v] && dist[v] < minDist) {
                minDist = dist[v];
                u = v;
            }
        }

        if (u == -1) break;

        visited[u] = true;

        // Update distances
        for (int v = 0; v < numVertices; v++) {
            if (!visited[v] && graph[u][v] != 0 && dist[u] != INF) {
                int newDist = dist[u] + graph[u][v];
                if (newDist < dist[v]) {
                    dist[v] = newDist;
                }
            }
        }
    }

    printf("Vertex\tDistance from Source\n");
    for (int i = 0; i < numVertices; i++) {
        printf("%d\t%d\n", i, dist[i]);
    }
}

int main() {
    int graph[MAX_VERTICES][MAX_VERTICES] = {
        {0, 4, 2, 0, 0, 0},
        {4, 0, 0, 1, 6, 0},
        {2, 0, 0, 0, 3, 0},
        {0, 1, 0, 0, 0, 2},
        {0, 6, 3, 0, 0, 5},
        {0, 0, 0, 2, 5, 0}
    };

    dijkstra(graph, 6, 0);

    return 0;
}

C++ Implementation

#include <iostream>
#include <vector>
#include <queue>
#include <limits>
using namespace std;

const int INF = numeric_limits<int>::max();

class Graph {
private:
    int numVertices;
    vector<vector<pair<int, int>>> adjList;  // {neighbor, weight}

public:
    Graph(int vertices) : numVertices(vertices), adjList(vertices) {}

    void addEdge(int src, int dest, int weight) {
        adjList[src].push_back({dest, weight});
        adjList[dest].push_back({src, weight});  // Undirected
    }

    void dijkstra(int source) {
        vector<int> dist(numVertices, INF);
        vector<int> parent(numVertices, -1);

        // Min-heap: {distance, vertex}
        priority_queue<pair<int, int>, vector<pair<int, int>>, greater<pair<int, int>>> pq;

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

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

            // Skip if we've already found a shorter path
            if (d > dist[u]) continue;

            for (auto& edge : adjList[u]) {
                int v = edge.first;
                int weight = edge.second;

                if (dist[u] + weight < dist[v]) {
                    dist[v] = dist[u] + weight;
                    parent[v] = u;
                    pq.push({dist[v], v});
                }
            }
        }

        printSolution(dist, parent, source);
    }

    void printSolution(vector<int>& dist, vector<int>& parent, int source) {
        cout << "Vertex\tDistance\tPath" << endl;
        for (int i = 0; i < numVertices; i++) {
            cout << i << "\t" << dist[i] << "\t\t";
            printPath(parent, i);
            cout << endl;
        }
    }

    void printPath(vector<int>& parent, int vertex) {
        if (parent[vertex] == -1) {
            cout << vertex;
            return;
        }
        printPath(parent, parent[vertex]);
        cout << " -> " << vertex;
    }
};

int main() {
    Graph graph(6);

    graph.addEdge(0, 1, 4);
    graph.addEdge(0, 2, 2);
    graph.addEdge(1, 3, 1);
    graph.addEdge(1, 4, 6);
    graph.addEdge(2, 4, 3);
    graph.addEdge(3, 5, 2);
    graph.addEdge(4, 5, 5);

    graph.dijkstra(0);

    return 0;
}

Java Implementation

import java.util.*;

class Graph {
    private int numVertices;
    private List<List<Edge>> adjList;

    static class Edge {
        int dest, weight;

        Edge(int dest, int weight) {
            this.dest = dest;
            this.weight = weight;
        }
    }

    static class Node implements Comparable<Node> {
        int vertex, dist;

        Node(int vertex, int dist) {
            this.vertex = vertex;
            this.dist = dist;
        }

        public int compareTo(Node other) {
            return Integer.compare(this.dist, other.dist);
        }
    }

    public Graph(int vertices) {
        numVertices = vertices;
        adjList = new ArrayList<>(vertices);
        for (int i = 0; i < vertices; i++) {
            adjList.add(new ArrayList<>());
        }
    }

    public void addEdge(int src, int dest, int weight) {
        adjList.get(src).add(new Edge(dest, weight));
        adjList.get(dest).add(new Edge(src, weight));
    }

    public void dijkstra(int source) {
        int[] dist = new int[numVertices];
        int[] parent = new int[numVertices];
        Arrays.fill(dist, Integer.MAX_VALUE);
        Arrays.fill(parent, -1);

        PriorityQueue<Node> pq = new PriorityQueue<>();
        dist[source] = 0;
        pq.offer(new Node(source, 0));

        while (!pq.isEmpty()) {
            Node current = pq.poll();
            int u = current.vertex;

            if (current.dist > dist[u]) continue;

            for (Edge edge : adjList.get(u)) {
                int v = edge.dest;
                int weight = edge.weight;

                if (dist[u] + weight < dist[v]) {
                    dist[v] = dist[u] + weight;
                    parent[v] = u;
                    pq.offer(new Node(v, dist[v]));
                }
            }
        }

        printSolution(dist, parent, source);
    }

    private void printSolution(int[] dist, int[] parent, int source) {
        System.out.println("Vertex\tDistance\tPath");
        for (int i = 0; i < numVertices; i++) {
            System.out.print(i + "\t" + dist[i] + "\t\t");
            printPath(parent, i);
            System.out.println();
        }
    }

    private void printPath(int[] parent, int vertex) {
        if (parent[vertex] == -1) {
            System.out.print(vertex);
            return;
        }
        printPath(parent, parent[vertex]);
        System.out.print(" -> " + vertex);
    }

    public static void main(String[] args) {
        Graph graph = new Graph(6);

        graph.addEdge(0, 1, 4);
        graph.addEdge(0, 2, 2);
        graph.addEdge(1, 3, 1);
        graph.addEdge(1, 4, 6);
        graph.addEdge(2, 4, 3);
        graph.addEdge(3, 5, 2);
        graph.addEdge(4, 5, 5);

        graph.dijkstra(0);
    }
}

Complexity Analysis

Time Complexity:
- With array: O(V²)
- With binary heap: O((V + E) log V)
- With Fibonacci heap: O(E + V log V)
Space Complexity: O(V)
Limitation: Cannot handle negative edge weights

Bellman-Ford Algorithm

Bellman-Ford finds shortest paths even with negative edge weights and can detect negative cycles.

Algorithm

1. Initialize:
   - distance[source] = 0
   - distance[all others] = ∞

2. Relax all edges V-1 times:
   For each edge (u, v) with weight w:
     if distance[u] + w < distance[v]:
       distance[v] = distance[u] + w

3. Check for negative cycles:
   For each edge (u, v) with weight w:
     if distance[u] + w < distance[v]:
       return "Negative cycle exists"

C++ Implementation

#include <iostream>
#include <vector>
#include <limits>
using namespace std;

const int INF = numeric_limits<int>::max();

struct Edge {
    int src, dest, weight;
};

class Graph {
private:
    int numVertices;
    vector<Edge> edges;

public:
    Graph(int vertices) : numVertices(vertices) {}

    void addEdge(int src, int dest, int weight) {
        edges.push_back({src, dest, weight});
    }

    bool bellmanFord(int source) {
        vector<int> dist(numVertices, INF);
        vector<int> parent(numVertices, -1);

        dist[source] = 0;

        // Relax all edges V-1 times
        for (int i = 0; i < numVertices - 1; i++) {
            for (const Edge& edge : edges) {
                if (dist[edge.src] != INF &&
                    dist[edge.src] + edge.weight < dist[edge.dest]) {
                    dist[edge.dest] = dist[edge.src] + edge.weight;
                    parent[edge.dest] = edge.src;
                }
            }
        }

        // Check for negative cycles
        for (const Edge& edge : edges) {
            if (dist[edge.src] != INF &&
                dist[edge.src] + edge.weight < dist[edge.dest]) {
                cout << "Graph contains negative cycle" << endl;
                return false;
            }
        }

        printSolution(dist, parent);
        return true;
    }

    void printSolution(vector<int>& dist, vector<int>& parent) {
        cout << "Vertex\tDistance from Source" << endl;
        for (int i = 0; i < numVertices; i++) {
            cout << i << "\t" << dist[i] << endl;
        }
    }
};

int main() {
    Graph graph(5);

    graph.addEdge(0, 1, -1);
    graph.addEdge(0, 2, 4);
    graph.addEdge(1, 2, 3);
    graph.addEdge(1, 3, 2);
    graph.addEdge(1, 4, 2);
    graph.addEdge(3, 2, 5);
    graph.addEdge(3, 1, 1);
    graph.addEdge(4, 3, -3);

    graph.bellmanFord(0);

    return 0;
}

Complexity Analysis

Time Complexity: O(V × E)
Space Complexity: O(V)
Advantages: Handles negative weights, detects negative cycles
Disadvantages: Slower than Dijkstra

Minimum Spanning Tree (MST)

Problem Definition

Minimum Spanning Tree: A subset of edges that connects all vertices with minimum total edge weight, forming a tree (no cycles).

Graph with weights:
    1 ---2--- 2
    |         |
    4         3
    |         |
    3 ---1--- 4

MST (total weight = 6):
    1 ---2--- 2
              |
              3
              |
    3 ---1--- 4

Prim's Algorithm

Prim's algorithm builds MST by starting from one vertex and greedily adding the minimum weight edge that connects a new vertex.

Algorithm

1. Start with arbitrary vertex in MST
2. While MST doesn't include all vertices:
   a. Find minimum weight edge connecting MST to non-MST vertex
   b. Add this edge and vertex to MST

C++ Implementation

#include <iostream>
#include <vector>
#include <queue>
#include <limits>
using namespace std;

const int INF = numeric_limits<int>::max();

class Graph {
private:
    int numVertices;
    vector<vector<pair<int, int>>> adjList;

public:
    Graph(int vertices) : numVertices(vertices), adjList(vertices) {}

    void addEdge(int src, int dest, int weight) {
        adjList[src].push_back({dest, weight});
        adjList[dest].push_back({src, weight});
    }

    void primMST() {
        vector<int> key(numVertices, INF);
        vector<int> parent(numVertices, -1);
        vector<bool> inMST(numVertices, false);

        // Min-heap: {key, vertex}
        priority_queue<pair<int, int>, vector<pair<int, int>>, greater<pair<int, int>>> pq;

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

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

            if (inMST[u]) continue;

            inMST[u] = true;

            for (auto& edge : adjList[u]) {
                int v = edge.first;
                int weight = edge.second;

                if (!inMST[v] && weight < key[v]) {
                    key[v] = weight;
                    parent[v] = u;
                    pq.push({key[v], v});
                }
            }
        }

        printMST(parent, key);
    }

    void printMST(vector<int>& parent, vector<int>& key) {
        int totalWeight = 0;
        cout << "Edge\tWeight" << endl;
        for (int i = 1; i < numVertices; i++) {
            cout << parent[i] << " - " << i << "\t" << key[i] << endl;
            totalWeight += key[i];
        }
        cout << "Total MST weight: " << totalWeight << endl;
    }
};

int main() {
    Graph graph(5);

    graph.addEdge(0, 1, 2);
    graph.addEdge(0, 3, 6);
    graph.addEdge(1, 2, 3);
    graph.addEdge(1, 3, 8);
    graph.addEdge(1, 4, 5);
    graph.addEdge(2, 4, 7);
    graph.addEdge(3, 4, 9);

    graph.primMST();

    return 0;
}

Complexity

Time: O(E log V) with priority queue
Space: O(V)

Kruskal's Algorithm

Kruskal's algorithm builds MST by sorting all edges and adding them in increasing weight order, avoiding cycles (uses Union-Find).

Algorithm

1. Sort all edges by weight
2. For each edge in sorted order:
   a. If adding edge doesn't create cycle:
      - Add edge to MST
   b. Stop when MST has V-1 edges

C++ Implementation with Union-Find

#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;

struct Edge {
    int src, dest, weight;

    bool operator<(const Edge& other) const {
        return weight < other.weight;
    }
};

class UnionFind {
private:
    vector<int> parent, rank;

public:
    UnionFind(int n) : parent(n), rank(n, 0) {
        for (int i = 0; i < n; i++) {
            parent[i] = i;
        }
    }

    int find(int x) {
        if (parent[x] != x) {
            parent[x] = find(parent[x]);  // Path compression
        }
        return parent[x];
    }

    bool unite(int x, int y) {
        int rootX = find(x);
        int rootY = find(y);

        if (rootX == rootY) return false;

        // Union by rank
        if (rank[rootX] < rank[rootY]) {
            parent[rootX] = rootY;
        }
        else if (rank[rootX] > rank[rootY]) {
            parent[rootY] = rootX;
        }
        else {
            parent[rootY] = rootX;
            rank[rootX]++;
        }

        return true;
    }
};

class Graph {
private:
    int numVertices;
    vector<Edge> edges;

public:
    Graph(int vertices) : numVertices(vertices) {}

    void addEdge(int src, int dest, int weight) {
        edges.push_back({src, dest, weight});
    }

    void kruskalMST() {
        sort(edges.begin(), edges.end());

        UnionFind uf(numVertices);
        vector<Edge> mst;
        int totalWeight = 0;

        for (const Edge& edge : edges) {
            if (uf.unite(edge.src, edge.dest)) {
                mst.push_back(edge);
                totalWeight += edge.weight;

                if (mst.size() == numVertices - 1) {
                    break;
                }
            }
        }

        cout << "Edge\tWeight" << endl;
        for (const Edge& edge : mst) {
            cout << edge.src << " - " << edge.dest << "\t" << edge.weight << endl;
        }
        cout << "Total MST weight: " << totalWeight << endl;
    }
};

int main() {
    Graph graph(5);

    graph.addEdge(0, 1, 2);
    graph.addEdge(0, 3, 6);
    graph.addEdge(1, 2, 3);
    graph.addEdge(1, 3, 8);
    graph.addEdge(1, 4, 5);
    graph.addEdge(2, 4, 7);
    graph.addEdge(3, 4, 9);

    graph.kruskalMST();

    return 0;
}

Complexity

Time: O(E log E) for sorting
Space: O(V + E)

Algorithm Comparison

Algorithm	Problem	Time	Space	Notes
Dijkstra	Single-source shortest path	O(E log V)	O(V)	No negative weights
Bellman-Ford	Single-source shortest path	O(VE)	O(V)	Handles negative weights
Prim's	MST	O(E log V)	O(V)	Good for dense graphs
Kruskal's	MST	O(E log E)	O(V+E)	Good for sparse graphs

Common Mistakes

Using Dijkstra with negative weights - Wrong results
Not checking for negative cycles - Bellman-Ford
Wrong priority queue comparator - Max-heap instead of min-heap
Forgetting path compression - Union-Find inefficiency
Not sorting edges - Kruskal's algorithm
Infinite loop in Dijkstra - Not marking visited properly
Integer overflow - Using INT_MAX in distance calculations

Debugging Tips

Print intermediate states - Distance arrays, MST edges
Test with small graphs - Trace by hand
Verify heap operations - Check min-heap property
Check edge cases - Disconnected graphs, single vertex
Validate Union-Find - Test find and unite separately
Use visual tools - Graph visualization libraries
Compare with known solutions - Standard test cases

Mini Exercises

Implement Dijkstra with different data structures
Detect negative cycle using Bellman-Ford
Find second shortest path
Implement A* search algorithm
Compare Prim's and Kruskal's on same graph
Find MST weight without building the tree
Implement bidirectional Dijkstra
Solve all-pairs shortest paths (Floyd-Warshall)
Find critical edges in MST
Implement parallel Bellman-Ford

Review Questions

Why can't Dijkstra handle negative weights?
When would you use Bellman-Ford over Dijkstra?
What's the difference between Prim's and Kruskal's?
How does Union-Find help in Kruskal's algorithm?
What problems can be solved with MST?

Reference Checklist

By the end of this chapter, you should be able to:

Implement Dijkstra's algorithm
Implement Bellman-Ford algorithm
Implement Prim's MST algorithm
Implement Kruskal's MST algorithm
Use Union-Find data structure
Choose appropriate algorithm for the problem
Analyze time and space complexity
Handle edge cases and negative weights

Next Steps

Chapter 14 explores mathematical algorithms—GCD, LCM, prime number generation, modular arithmetic, and number theory fundamentals essential for cryptography and competitive programming.

Key Takeaway: Graph algorithms solve optimization problems on weighted graphs. Dijkstra and Bellman-Ford find shortest paths (with different constraints). Prim's and Kruskal's find minimum spanning trees (with different approaches). Understanding when to use each algorithm is crucial for efficient problem-solving.