REFERENCE SHEET

Graph traversal & shortest paths

Choose a traversal based on edge weights, direction, and the question being asked.

Before this Data structures & amortized cost, Asymptotics & recurrences

relax(u,v): d[v] ← min(d[v], d[u]+w(u,v))

Definitions

Graph

G=(V,E) has vertices and edges; edges may be directed or undirected and may carry weights. A path follows consecutive edges.

BFS and DFS

Breadth-first search uses a queue to explore layers. Depth-first search follows a branch before backtracking, using recursion or a stack.

Shortest-path distance

The minimum total edge weight over source-to-target paths when a finite minimum exists. Unreachable vertices have distance +∞.

Key theorems

BFS guarantee

On an unweighted graph, BFS finds minimum-edge-count distances from a source. With adjacency lists, its time is O(|V|+|E|).

Dijkstra guarantee

For nonnegative edge weights, repeatedly settling the smallest tentative distance and relaxing outgoing edges yields shortest paths. A binary-heap implementation takes O((|V|+|E|) log |V|).

DAG shortest paths

In a directed acyclic graph, relax vertices in topological order in O(|V|+|E|). Negative weights are allowed because there are no directed cycles.

Notable applications

Routing

Shortest paths model travel, communication, and navigation costs.

Dependencies

A topological ordering schedules prerequisites in a DAG; no such ordering exists when a directed cycle is present.

Work it out

Try before revealing

01 / Compute

Edges are s→a of weight 4, s→b of weight 1, b→a of weight 2, and a→t of weight 1. Find the shortest path from s to t.

Hint

Compare reaching a directly with reaching it through b.

Solution

s→b→a→t costs 1+2+1=4, beating s→a→t of cost 5.

02 / Explain

Why can BFS fail for weighted shortest paths? Use s→t of weight 10 and s→a→t with each edge of weight 1.