Essential Graph Algorithms: Complete Reference

TL;DR

• Bottom line: The essential graph algorithms are BFS and DFS for traversal, Dijkstra and Bellman-Ford for shortest paths, A* for heuristic search, Floyd-Warshall for all-pairs shortest paths, Kruskal and Prim for MST, topological sort for DAG ordering, and Tarjan/Kosaraju for SCCs.
• Key tool/command: from collections import deque; deque() for BFS, heapq for Dijkstra
• Watch out for: Using Dijkstra on graphs with negative edge weights -- it produces incorrect results silently.
• Works with: Any language with arrays, queues, and priority queues. Language-agnostic algorithms dating to 1956.

Constraints

• Dijkstra's algorithm requires non-negative edge weights; use Bellman-Ford for graphs with negative edges
• A* requires an admissible heuristic (h(n) <= actual cost) to guarantee optimal shortest paths
• Topological sort is only defined for DAGs; if the graph has cycles, no valid ordering exists
• Floyd-Warshall uses O(V³) time and O(V²) space -- impractical for V > ~5,000
• BFS only finds shortest paths in unweighted or unit-weight graphs; for weighted graphs, use Dijkstra or Bellman-Ford

Quick Reference

Decision Tree

START: What problem are you solving?
+-- Shortest path?
|   +-- Single source?
|   |   +-- Unweighted graph?
|   |   |   +-- YES -> BFS (O(V+E))
|   |   +-- Weighted, no negative edges?
|   |   |   +-- Need heuristic speedup to single target?
|   |   |   |   +-- YES -> A* with admissible heuristic
|   |   |   +-- NO -> Dijkstra with binary heap (O((V+E) log V))
|   |   +-- Negative edges possible?
|   |       +-- YES -> Bellman-Ford (O(VE)), detects negative cycles
|   +-- All pairs?
|       +-- Dense graph (E ~ V^2)?
|       |   +-- YES -> Floyd-Warshall (O(V^3))
|       +-- Sparse graph?
|           +-- Run Dijkstra from each vertex (O(V(V+E) log V))
+-- Minimum spanning tree?
|   +-- Sparse graph (E << V^2)?
|   |   +-- YES -> Kruskal (O(E log E)) with Union-Find
|   +-- Dense graph (E ~ V^2)?
|       +-- YES -> Prim with binary heap (O((V+E) log V))
+-- Traversal / Search?
|   +-- Need shortest path or level-order?
|   |   +-- YES -> BFS
|   +-- Need to explore deeply (backtracking, cycle detection)?
|       +-- YES -> DFS
+-- Topological ordering?
|   +-- DAG confirmed -> Kahn's algorithm or DFS-based topo sort
+-- Strongly connected components?
|   +-- Need single-pass? -> Tarjan's algorithm
|   +-- Two-pass acceptable? -> Kosaraju's algorithm (simpler)
+-- Cycle detection?
    +-- Directed graph -> DFS with coloring (white/gray/black)
    +-- Undirected graph -> DFS with parent tracking or Union-Find

Step-by-Step Guide

1. Represent the graph with an adjacency list

An adjacency list uses O(V + E) space and supports efficient neighbor iteration. Adjacency matrices use O(V²) and are only preferred for dense graphs. [src1]

from collections import defaultdict

# Unweighted graph
graph = defaultdict(list)
edges = [(0, 1), (0, 2), (1, 3), (2, 3)]
for u, v in edges:
    graph[u].append(v)
    graph[v].append(u)  # omit for directed graph

# Weighted graph
weighted_graph = defaultdict(list)
weighted_edges = [(0, 1, 4), (0, 2, 1), (1, 3, 1), (2, 3, 5)]
for u, v, w in weighted_edges:
    weighted_graph[u].append((v, w))
    weighted_graph[v].append((u, w))  # omit for directed graph

Verify: len(graph[0]) -> expected: 2

2. Implement BFS for shortest path in unweighted graphs

BFS explores nodes level by level using a FIFO queue. It finds the shortest path (fewest edges) from source to all reachable nodes. Time: O(V + E). [src2]

from collections import deque

def bfs_shortest_path(graph, start, end):
    queue = deque([(start, [start])])
    visited = {start}
    while queue:
        node, path = queue.popleft()
        if node == end:
            return path
        for neighbor in graph[node]:
            if neighbor not in visited:
                visited.add(neighbor)
                queue.append((neighbor, path + [neighbor]))
    return None  # no path exists

Verify: bfs_shortest_path(graph, 0, 3) -> expected: [0, 1, 3] or [0, 2, 3]

3. Implement Dijkstra for weighted shortest paths

Dijkstra uses a min-heap to always process the node with smallest known distance. Requires non-negative edge weights. [src4]

import heapq

def dijkstra(graph, start):
    dist = {start: 0}
    heap = [(0, start)]
    prev = {}
    while heap:
        d, u = heapq.heappop(heap)
        if d > dist.get(u, float('inf')):
            continue  # stale entry
        for v, weight in graph[u]:
            new_dist = d + weight
            if new_dist < dist.get(v, float('inf')):
                dist[v] = new_dist
                prev[v] = u
                heapq.heappush(heap, (new_dist, v))
    return dist, prev

Verify: dijkstra(weighted_graph, 0) -> dist: {0: 0, 1: 4, 2: 1, 3: 5}

4. Implement DFS for traversal and cycle detection

DFS explores as deep as possible before backtracking. For cycle detection in directed graphs, use three-color marking. [src3]

def dfs_iterative(graph, start):
    visited = set()
    stack = [start]
    order = []
    while stack:
        node = stack.pop()
        if node in visited:
            continue
        visited.add(node)
        order.append(node)
        for neighbor in reversed(graph[node]):
            if neighbor not in visited:
                stack.append(neighbor)
    return order

Verify: dfs_iterative(graph, 0) -> visits all reachable nodes from 0

5. Implement Kruskal's MST with Union-Find

Sort all edges by weight, then greedily add each edge if it does not form a cycle (via Union-Find). Time: O(E log E). [src6]

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

def kruskal(num_nodes, edges):
    edges.sort()  # sort by weight
    uf = UnionFind(num_nodes)
    mst, total = [], 0
    for w, u, v in edges:
        if uf.union(u, v):
            mst.append((u, v, w))
            total += w
            if len(mst) == num_nodes - 1: break
    return mst, total

Verify: MST of 4 nodes -> total weight: 3

Code Examples

Python: Bellman-Ford with negative cycle detection

# Input:  weighted directed graph as edge list, source vertex
# Output: shortest distances list, or raises ValueError on negative cycle

def bellman_ford(num_nodes, edges, source):
    dist = [float('inf')] * num_nodes
    dist[source] = 0
    for _ in range(num_nodes - 1):
        for u, v, w in edges:
            if dist[u] + w < dist[v]:
                dist[v] = dist[u] + w
    for u, v, w in edges:
        if dist[u] + w < dist[v]:
            raise ValueError("Negative-weight cycle detected")
    return dist

JavaScript: BFS shortest path

// Input:  adjacency list (Map), start node, end node
// Output: shortest path array, or null if no path exists

function bfsShortestPath(graph, start, end) {
  const queue = [[start, [start]]];
  const visited = new Set([start]);
  while (queue.length > 0) {
    const [node, path] = queue.shift();
    if (node === end) return path;
    for (const neighbor of (graph.get(node) || [])) {
      if (!visited.has(neighbor)) {
        visited.add(neighbor);
        queue.push([neighbor, [...path, neighbor]]);
      }
    }
  }
  return null;
}

Java: Dijkstra with priority queue

// Input:  adjacency list, source vertex, number of nodes
// Output: int[] of shortest distances from source

public static int[] dijkstra(List<List<int[]>> graph, int src, int n) {
    int[] dist = new int[n];
    Arrays.fill(dist, Integer.MAX_VALUE);
    dist[src] = 0;
    PriorityQueue<int[]> pq = new PriorityQueue<>((a, b) -> a[0] - b[0]);
    pq.offer(new int[]{0, src});
    while (!pq.isEmpty()) {
        int[] curr = pq.poll();
        int d = curr[0], u = curr[1];
        if (d > dist[u]) continue;
        for (int[] edge : graph.get(u)) {
            int v = edge[0], w = edge[1];
            if (dist[u] + w < dist[v]) {
                dist[v] = dist[u] + w;
                pq.offer(new int[]{dist[v], v});
            }
        }
    }
    return dist;
}

Go: Topological sort (Kahn's algorithm)

// Input:  number of nodes, adjacency list ([][]int)
// Output: topological order slice, or error if cycle exists

func topologicalSort(n int, graph [][]int) ([]int, error) {
    inDegree := make([]int, n)
    for u := 0; u < n; u++ {
        for _, v := range graph[u] {
            inDegree[v]++
        }
    }
    queue := []int{}
    for i, d := range inDegree {
        if d == 0 { queue = append(queue, i) }
    }
    order := []int{}
    for len(queue) > 0 {
        u := queue[0]; queue = queue[1:]
        order = append(order, u)
        for _, v := range graph[u] {
            inDegree[v]--
            if inDegree[v] == 0 { queue = append(queue, v) }
        }
    }
    if len(order) != n {
        return nil, fmt.Errorf("cycle detected")
    }
    return order, nil
}

Anti-Patterns

Wrong: Using Dijkstra on graphs with negative edges

# BAD -- Dijkstra silently produces wrong results with negative weights
graph = {0: [(1, 4), (2, 5)], 1: [], 2: [(1, -3)]}
dist, _ = dijkstra(graph, 0)  # Returns dist[1]=4, WRONG (actual: 2)

Correct: Use Bellman-Ford for negative edges

# GOOD -- Bellman-Ford handles negative edges correctly
edges = [(0, 1, 4), (0, 2, 5), (2, 1, -3)]
dist = bellman_ford(3, edges, 0)  # Returns dist[1]=2, CORRECT

Wrong: Using DFS for shortest path in unweighted graphs

# BAD -- DFS does NOT guarantee shortest path
def dfs_path(graph, start, end, visited=None):
    if visited is None: visited = set()
    visited.add(start)
    if start == end: return [start]
    for neighbor in graph[start]:
        if neighbor not in visited:
            path = dfs_path(graph, neighbor, end, visited)
            if path: return [start] + path
    return None  # May return longer path!

Correct: Use BFS for shortest path in unweighted graphs

# GOOD -- BFS guarantees shortest path (fewest edges)
path = bfs_shortest_path(graph, 0, 1)  # Always optimal

Wrong: Using adjacency matrix for sparse graphs

# BAD -- O(V^2) space waste; for V=100K, this uses ~40GB
adj_matrix = [[0] * V for _ in range(V)]

Correct: Use adjacency list for sparse graphs

# GOOD -- O(V + E) space, O(degree) neighbor iteration
from collections import defaultdict
adj_list = defaultdict(list)

Wrong: Forgetting to handle disconnected components

# BAD -- only traverses one component
visited = set()
queue = deque([start])
# ... misses disconnected nodes!

Correct: Iterate over all nodes for disconnected graphs

# GOOD -- iterate all nodes to find every component
for node in range(num_nodes):
    if node not in visited:
        bfs_from(node)  # starts new component traversal

Common Pitfalls

• Stale priority queue entries in Dijkstra: Old entries remain in the heap after distance updates. Fix: check if d > dist[u]: continue after popping. [src4]
• Stack overflow in recursive DFS: Python's default recursion limit is 1000. Fix: use iterative DFS with explicit stack. [src3]
• Confusing directed and undirected edge insertion: Adding only graph[u].append(v) makes the graph directed. Fix: clarify graph type before building adjacency list. [src5]
• Off-by-one in node indexing: CP problems often use 1-indexed nodes. Fix: allocate arrays of size n + 1 for 1-indexed, or normalize to 0-indexed. [src5]
• Not detecting negative cycles: V-1 Bellman-Ford passes find shortest paths but miss negative cycles. Fix: run one more pass; if any distance decreases, a negative cycle exists. [src8]
• Using Prim on disconnected graphs: Prim finds MST for one component only. Fix: check connectivity first or run Prim per component. [src6]
• Missing visited set in BFS/DFS: Without marking visited nodes, algorithms loop infinitely on cycles. Fix: mark nodes visited when discovered (enqueued), not when processed. [src2]

When to Use / When Not to Use

Important Caveats

• Production code should prefer graph libraries (NetworkX, JGraphT, Boost.Graph) over hand-rolled implementations; custom implementations are mainly for competitive programming, interviews, or performance-critical paths.
• A* performance depends on heuristic quality: Manhattan distance for grids, Euclidean for geometric graphs; a zero heuristic degrades A* to Dijkstra.
• Parallel/distributed graph algorithms (Pregel, GraphX) behave differently from sequential versions and require separate study.
• Priority queue choice matters: Fibonacci heap gives best theoretical Dijkstra complexity O(E + V log V) but binary heap O((V+E) log V) is faster in practice for most graphs.