Skip to main content

Graph Algorithms

TL;DR​

Dijkstra finds shortest paths in weighted graphs with non-negative weights using greedy selection (O(E log V) with min-heap). Bellman-Ford handles negative weights but runs slower (O(VE)). Kruskal's algorithm builds MST by sorting edges and using union-find (O(E log E)). Prim's algorithm builds MST from vertex incrementally (O(E log V)). Topological sort orders DAG vertices respecting dependencies: Kahn's algorithm uses in-degree counting (O(V + E)), DFS-based variant uses post-order (O(V + E)). Choose algorithms based on graph properties and requirements.

Core Concepts​

Shortest Path Problem​

Shortest path finds minimum-cost route from source to target vertex. Choice of algorithm depends on graph properties:

Graph properties affecting choice:

  • Weighted vs unweighted: BFS for unweighted, Dijkstra/Bellman-Ford for weighted
  • Non-negative vs negative weights: Dijkstra for non-negative, Bellman-Ford for negative
  • Single-source vs all-pairs: Dijkstra/Bellman-Ford for single-source, Floyd-Warshall for all-pairs
  • Sparse vs dense: O(E log V) preferred for sparse, O(V²) acceptable for dense

Dijkstra's Algorithm​

Dijkstra greedily selects unvisited vertex with minimum distance, updating neighbor distances.

Key properties:

  • Time complexity: O(E log V) with binary heap, O(V²) with array
  • Correctness: Greedy choice always optimal for non-negative weights
  • Guarantee: Finds shortest path from source to all vertices
  • Limitations: Cannot handle negative edge weights

Invariant: At each iteration, selected vertex has correct shortest distance from source (never improves).

Bellman-Ford Algorithm​

Bellman-Ford relaxes all edges repeatedly, detecting negative cycles.

Key properties:

  • Time complexity: O(VE) - relaxes all edges V-1 times
  • Correctness: Works with negative weights
  • Cycle detection: Can detect negative cycles (unfixable shortest paths)
  • Trade-off: Slower than Dijkstra but more general

Relaxation: For each edge (u, v) with weight w, if dist[u] + w < dist[v], update dist[v].

Minimum Spanning Tree (MST)​

MST connects all vertices with minimum total edge weight, forming a tree (V vertices, V-1 edges).

Properties:

  • Unique if weights distinct: Multiple MSTs possible with equal total weights
  • Cut property: Minimum weight edge crossing any cut is in some MST
  • Cycle property: Maximum weight edge in any cycle is not in MST

Kruskal's Algorithm​

Kruskal sorts edges by weight and adds edges without creating cycles (union-find).

Algorithm:

  1. Sort edges by weight
  2. Initialize each vertex as separate component
  3. For each edge in sorted order:
    • If endpoints in different components, add edge to MST
    • Union the two components

Time complexity: O(E log E) for sorting, O(E α(V)) for union-find operations.

Prim's Algorithm​

Prim grows MST from single vertex, always adding minimum weight edge to unvisited vertex.

Algorithm:

  1. Start from arbitrary vertex
  2. Mark as visited
  3. While unvisited vertices remain:
    • Find minimum weight edge from visited to unvisited
    • Add edge to MST and mark target as visited

Time complexity: O(E log V) with min-heap, O(V²) with array.

Topological Sorting​

Topological sort orders DAG vertices such that for every directed edge u → v, u comes before v in ordering.

Applications:

  • Task scheduling with dependencies
  • Dependency resolution in build systems
  • Instruction ordering in compilers

Constraint: Only possible for DAGs; cyclic graphs have no topological order.

Key Algorithms​

Dijkstra's Shortest Path​

Greedy algorithm maintaining distance estimates, repeatedly selecting closest unvisited vertex.

Bellman-Ford Shortest Path​

Dynamic programming approach relaxing edges multiple times, handling negative weights and detecting negative cycles.

Kruskal's MST​

Sort-based approach using union-find to efficiently detect cycle formation.

Prim's MST​

Greedy growing from single vertex, maintaining priority queue of edge candidates.

Topological Sort (Kahn's Algorithm)​

In-degree based approach: repeatedly remove vertices with in-degree zero.

Practical Example​

import heapq
from collections import defaultdict, deque

class WeightedGraph:
    def __init__(self):
        self.graph = defaultdict(list)
        self.vertices = set()

    def add_edge(self, u, v, weight):
        self.graph[u].append((v, weight))
        self.graph[v].append((u, weight))  # Undirected for MST
        self.vertices.add(u)
        self.vertices.add(v)

    # Dijkstra's Algorithm
    def dijkstra(self, start):
        distances = {v: float('inf') for v in self.vertices}
        distances[start] = 0
        pq = [(0, start)]
        visited = set()

        while pq:
            curr_dist, u = heapq.heappop(pq)

            if u in visited:
                continue
            visited.add(u)

            for v, weight in self.graph[u]:
                if v not in visited and distances[u] + weight < distances[v]:
                    distances[v] = distances[u] + weight
                    heapq.heappush(pq, (distances[v], v))

        return distances

    # Bellman-Ford Algorithm
    def bellman_ford(self, start):
        distances = {v: float('inf') for v in self.vertices}
        distances[start] = 0
        edges = []

        for u in self.graph:
            for v, weight in self.graph[u]:
                edges.append((u, v, weight))

        # Relax edges V-1 times
        for _ in range(len(self.vertices) - 1):
            for u, v, weight in edges:
                if distances[u] != float('inf') and distances[u] + weight < distances[v]:
                    distances[v] = distances[u] + weight

        # Detect negative cycles
        for u, v, weight in edges:
            if distances[u] != float('inf') and distances[u] + weight < distances[v]:
                return None  # Negative cycle detected

        return distances

    # Kruskal's MST
    def kruskal_mst(self):
        class UnionFind:
            def __init__(self, n):
                self.parent = list(range(n))
                self.rank = [0] * n

            def find(self, x):
                if self.parent[x] != x:
                    self.parent[x] = self.find(self.parent[x])
                return self.parent[x]

            def union(self, x, y):
                px, py = self.find(x), self.find(y)
                if px == py:
                    return False
                if self.rank[px] < self.rank[py]:
                    px, py = py, px
                self.parent[py] = px
                if self.rank[px] == self.rank[py]:
                    self.rank[px] += 1
                return True

        vertex_map = {v: i for i, v in enumerate(sorted(self.vertices))}
        uf = UnionFind(len(self.vertices))

        edges = []
        for u in self.graph:
            for v, weight in self.graph[u]:
                edges.append((weight, u, v))

        edges.sort()
        mst = []

        for weight, u, v in edges:
            u_idx, v_idx = vertex_map[u], vertex_map[v]
            if uf.union(u_idx, v_idx):
                mst.append((u, v, weight))

        return mst

    # Topological Sort (Kahn's Algorithm)
    def topological_sort(self):
        in_degree = defaultdict(int)
        graph = defaultdict(list)

        for u in self.graph:
            if u not in in_degree:
                in_degree[u] = 0
            for v, _ in self.graph[u]:
                graph[u].append(v)
                in_degree[v] += 1

        queue = deque([v for v in in_degree if in_degree[v] == 0])
        result = []

        while queue:
            u = queue.popleft()
            result.append(u)

            for v in graph[u]:
                in_degree[v] -= 1
                if in_degree[v] == 0:
                    queue.append(v)

        return result if len(result) == len(in_degree) else None

# Test
g = WeightedGraph()
edges = [(0, 1, 4), (0, 2, 2), (1, 2, 1), (1, 3, 5), (2, 3, 8), (2, 4, 10), (3, 4, 2)]
for u, v, w in edges:
    g.add_edge(u, v, w)

print("Dijkstra from 0:", g.dijkstra(0))
print("Bellman-Ford from 0:", g.bellman_ford(0))
print("Kruskal MST:", g.kruskal_mst())

Common Pitfalls​

warning

Using Dijkstra with negative weights: Dijkstra assumes greedy selection is optimal, failing with negative edges. Use Bellman-Ford instead.

Not handling disconnected graphs in MST: MST only works for connected graphs. Check connectivity before running MST algorithms.

Confusing directed and undirected edges: Topological sort requires directed graphs; MST requires undirected graphs. Mismatching breaks algorithms.

Inefficient MST with dense graphs: Kruskal has O(E log E) dominated by sorting; with E = O(V²), becomes O(V² log V). Prim's O(E log V) better for dense graphs.

Infinite distances in Bellman-Ford: Unreachable vertices stay at infinity. Forgetting to check causes incorrect relaxations or overflow errors.

Topological sort on cyclic graphs: Returns incomplete ordering; doesn't detect cycles. Verify DAG property first or check result length.

Self-Check​

  1. Why does Dijkstra fail with negative weights? What property does it assume?
  2. How are Kruskal and Prim different? When is each preferred?
  3. Can topological sort produce multiple valid orderings for same DAG? How?

One Takeaway​

info

Graph algorithms solve fundamental optimization problems. Dijkstra greedily finds shortest paths in non-negative weighted graphs (O(E log V)). MST algorithms connect all vertices minimally: Kruskal sorts edges and uses union-find, Prim grows from vertex with priority queue. Topological sort orders DAG dependencies using either in-degree counting or DFS post-order. Choosing the right algorithm based on graph properties and problem constraints is crucial for efficient solutions.

References​

  • Cormen, T. H., Leiserson, C. E., Rivest, R. L., & Stein, C. (2009). Introduction to Algorithms (3rd ed.). MIT Press.
  • Dijkstra, E. W. (1959). "A note on two problems in connexion with graphs." Numerische mathematik, 1(1), 269-271.
  • Kruskal, J. B. (1956). "On the shortest spanning subtree of a graph and the traveling salesman problem." PNAS, 48(6), 844-846.