Graph Algorithms

A graph is a set of nodes connected by edges. Edges can be directed or undirected, and they can carry weights representing cost or distance. Many real problems — routing, scheduling, dependency resolution, social networks — are graph problems in disguise.

Representing a Graph

The two common representations are:

• Adjacency list — for each node, store the list of its neighbors. Compact for sparse graphs (O(V + E) space) and the standard choice in practice.
• Adjacency matrix — a V × V table of booleans or weights. Constant-time edge lookup, but O(V²) space, which is wasteful when most nodes are not connected.

The example uses an adjacency list of (neighbor, weight) pairs.

Dijkstra's Algorithm

Dijkstra's algorithm finds the shortest path from a source node to every other node in a graph with non-negative edge weights. The idea: keep a tentative distance to every node, repeatedly pick the unvisited node with the smallest distance, and relax all its outgoing edges. With a priority queue (min-heap) the running time is O((V + E) log V).

The key invariant: once a node is popped from the priority queue, its shortest distance is final. This works only because all edge weights are non-negative — a negative edge could make a previously-finalized node reachable by a shorter path.

When to Use What

Pick the right algorithm for the graph:

• BFS — shortest path in an unweighted graph (O(V + E))
• Dijkstra — shortest path with non-negative weights
• Bellman-Ford — handles negative edge weights, detects negative cycles (O(V × E))
• Floyd-Warshall — all-pairs shortest paths in a small dense graph (O(V³))
• A* — heuristic-guided search for shortest paths with a goal node, faster than Dijkstra when a good heuristic exists

Tracking the Path Itself

Dijkstra as written above returns only the distances. To reconstruct the actual path, store a prev[v] parent pointer whenever you update dist[v], then walk backwards from the destination to the source.

Try It Yourself

• Modify the example to also return the parent map and reconstruct the path from A to D
• Add an edge D -> A with weight 1 and verify Dijkstra still terminates
• Implement BFS on the same graph and compare results when all weights are 1