Discrete Math › Section C · Graph theory › Topic C.10
Weighted graphs and shortest paths
Every route-planning app answers the same question thousands of times a second: what is the cheapest way from here to there? Breadth-first search answers it when every step costs the same, and Dijkstra's algorithm answers it when steps have different, non-negative costs.
Costs on the edges
A weighted graph gives every edge a number, its weight, such as a distance in kilometres, a travel time in minutes or a price in dollars. The length of a path is the sum of the weights of its edges, and the distance from \(s\) to \(t\) is the smallest length of any path between them. Edges can be undirected, like two-way roads, or directed, like one-way streets and flights; the methods below work for both. The cheapest path need not have the fewest edges: three short hops can beat one long road.
Equal costs: breadth-first search
When every edge costs the same, distance means the number of edges, and breadth-first search (BFS) finds it. Start at \(s\) with distance 0. Its neighbours get distance 1; their unvisited neighbours get distance 2; and so on, layer by layer, using a queue so that vertices are handled in the order discovered. With edges s-a, s-b, a-c, b-c, c-d, b-e and e-d, BFS from \(s\) gives a and b distance 1, c and e distance 2, and d distance 3. Depth-first search visits every vertex too, but its first route to a vertex can be needlessly long, so it does not find distances.
Dijkstra's idea
With unequal weights, Edsger Dijkstra's algorithm, published in 1959, keeps a tentative distance for every vertex: the length of the best path found so far. At the start, \(s\) has 0 and every other vertex has \(\infty\). At each step, the unfinished vertex with the smallest tentative distance is declared final, because, as a later card explains, no cheaper route to it can exist. Then each of its edges is used to try to improve its neighbours: if \(d(u) + w(u, v) < d(v)\), set \(d(v) = d(u) + w(u, v)\) and record \(u\) as the predecessor of \(v\). This update is called relaxing the edge.
The algorithm in steps
1. Set \(d(s) = 0\) and \(d(v) = \infty\) for all other vertices; mark every vertex unfinished. 2. Choose the unfinished vertex \(u\) with the smallest \(d(u)\) and mark it finished. 3. For each edge from \(u\) to an unfinished vertex \(v\), relax it:
4. Repeat steps 2 and 3 until every vertex is finished, or until the target is finished if you need only one route. Stored in a priority queue, the tentative distances make each choice in step 2 fast, and the whole run takes about \(O(E \log V)\) time on a connected graph.
Worked example: tracing Dijkstra
Roads, in minutes: SA 4, SB 2, AB 1, AC 5, BC 8, BD 10, CD 2, CT 6, DT 2. Start at S. 1. Finish S (0). Relax: A 4, B 2. 2. Finish B (2). Relax: A improves to 3 through B, C becomes 10, D becomes 12. 3. Finish A (3). Relax: C improves to \(3 + 5 = 8\). 4. Finish C (8). Relax: D improves to 10, T becomes 14. 5. Finish D (10). Relax: T improves to 12. 6. Finish T (12). The shortest time from S to T is 12 minutes. Notice that the direct road SA, at 4, lost to the two-road route S-B-A, at 3.
Reading off the route
Each time a distance improves, record the vertex it came from. In the example the final predecessors are: B from S, A from B, C from A, D from C and T from D. Follow them backwards from T: T, D, C, A, B, S. Reversed, the route is S-B-A-C-D-T, and its length checks out: \(2 + 1 + 5 + 2 + 2 = 12\). The predecessor edges together form a shortest-path tree, which holds a cheapest route from S to every vertex. Here it happens to match the minimum spanning tree from the topic on spanning trees, but in general the two differ: that tree minimises total edge weight, not distances from one starting vertex.
Why finished means final
Suppose \(u\) has the smallest tentative distance among unfinished vertices, and imagine some cheaper path from \(s\) to \(u\). That path starts among finished vertices and must leave them somewhere, at a first unfinished vertex \(x\). The part of the path up to \(x\) already costs at least \(d(x)\), which is at least \(d(u)\) because \(u\) was the smallest. The rest of the path, from \(x\) to \(u\), can only add weight, because no weight is negative. So the path costs at least \(d(u)\), not less. The whole argument depends on that word: non-negative.
Worked example: a negative weight breaks it
Take directed edges S to A with weight 2, S to B with weight 3, and B to A with weight \(-2\), perhaps a refund. 1. Dijkstra finishes S, then sets A to 2 and B to 3. 2. A has the smaller value, so it is finished at 2. 3. B is finished at 3, and its edge to A would give \(3 + (-2) = 1\), but A is already final and is not updated. 4. The true distance to A is 1, by S-B-A, so the algorithm's answer, 2, is wrong. The Bellman-Ford algorithm handles negative weights by relaxing every edge \(V - 1\) times, and it can also detect a negative cycle, around which costs would fall forever.
Beyond one starting point
To find distances between every pair of vertices, the Floyd-Warshall algorithm fills in a table in about \(V^3\) steps; it allows negative weights as long as there are no negative cycles. Navigation software on huge road networks adds tricks to Dijkstra's method. The A* algorithm, for example, adds an estimate of the remaining distance, such as the straight-line distance to the destination, so that it explores roads heading the right way first. All of these share Dijkstra's core move of relaxing edges to improve tentative distances.
Common mistakes to avoid
First, finishing a vertex because it was reached first rather than because its tentative distance is the smallest. Second, forgetting to relax: a vertex's value can fall several times, as D's did from 12 to 10. Third, using Dijkstra's algorithm with negative weights. Fourth, using BFS on a weighted graph, which minimises the number of edges, not the total weight. Fifth, confusing a shortest-path tree with a minimum spanning tree.
Key takeaways
In a weighted graph, a path's length is the sum of its weights, and the distance is the least such length. BFS finds distances when all edges cost the same. Dijkstra's algorithm repeatedly finishes the unfinished vertex with the smallest tentative distance and relaxes its edges; it is correct when no weight is negative. Predecessors record the routes and form a shortest-path tree. Bellman-Ford handles negative weights and detects negative cycles, Floyd-Warshall finds all pairs, and A* speeds up single routes with a good estimate.
Flashcards
Flashcard
Each edge carries a number such as a distance, time or cost
Test your understanding
Question 1 of 5
Edges: PQ 3, PR 1, RQ 1, QS 2, RS 6 (undirected). What is the shortest distance from P to S?
Question 2 of 5
Why can Dijkstra's algorithm give a wrong answer when some edge weight is negative?
Question 3 of 5
An unweighted graph has edges s-a, s-b, a-c, b-c, c-d, b-e and e-d. How many edges are on a shortest path from s to d?
Question 4 of 5
At each step, which vertex does Dijkstra's algorithm mark as finished?
Question 5 of 5
Run Dijkstra from P on the edges PQ 3, PR 1, RQ 1, QS 2, RS 6. What is the tentative distance of S immediately after R is finished and its edges are relaxed?
