Discrete Math · Undergraduate
Shortest Paths and Dijkstra's Algorithm
Quick answer
In a network whose edges carry lengths or costs, the shortest path between two vertices is the route with the smallest total weight. Dijkstra's algorithm finds the shortest distance from a starting vertex to every other vertex. It keeps a tentative distance for each vertex, repeatedly finalizes the closest unfinished one, and updates the distances of its neighbors. Recording where each improvement came from traces the paths themselves. It works whenever no edge weight is negative.
What you'll learn
- Describe the shortest path problem on a weighted graph
- Run Dijkstra's algorithm by hand with a table of tentative distances
- Recover a shortest path from the recorded predecessors
- Explain why negative weights break the algorithm
The cheapest route
Road maps, computer networks and flight schedules are weighted graphs: each edge has a length, a delay or a price. A shortest path between two vertices is a route whose edge weights add up to the least total. Dijkstra’s algorithm finds the shortest distance from one start vertex to all the others.
- Give the start distance and every other vertex distance .
- Pick the unfinished vertex with the smallest distance. Mark it final.
- For each neighbor, if the route through the final vertex is shorter than its current distance, lower the distance and record where it came from.
- Repeat until every vertex is final.
Why the closest vertex can be finalized
Suppose is the unfinished vertex with the smallest tentative distance. Any other route to must leave the finished region through some unfinished vertex , and is already at least as far as . With no negative edges, the rest of that route can only add length, so nothing beats ‘s current distance. Each round therefore settles one vertex for good. This is also why the algorithm fails with negative weights: a later edge could subtract length and undercut a distance already marked final.
Worked examples
Common mistakes
Practice problems
-
In the figure, what is the shortest distance from S to C?
Answer
Full solution
S–B–A–C: . The edge B–C gives .
-
In the figure, the weight of C–D changes to . What is the new distance from S to T?
Answer
Full solution
D is now reached via B for , and T via C for , less than .
-
Find the shortest distances from T to every other vertex in the figure.
Answer
D , C , A , B , S
Full solution
The edges have no direction, so the path from T to S reverses S–B–A–C–D–T.
-
In Example 1, in what order are the vertices finalized?
Answer
S, B, A, C, D, T
Full solution
Each round finalizes the unfinished vertex with the smallest distance: .
-
Triangle X, Y, Z has edges X–Y , X–Z and Z–Y . Find the shortest distance from X to Y.
Answer
Full solution
X–Z–Y costs , less than the direct edge.
-
The predecessor records in Example 1 form a tree. How many edges does it have?
Answer
Full solution
Each of the vertices other than S has one predecessor, and a tree on vertices has edges.
-
Can the shortest path from S to T use an edge of weight in the figure?
Answer
No
Full solution
B–D gives D the distance , but the route through C gives , and the shortest route to T does not pass through B–D.
-
A student marks A final at distance right after leaving S. What is wrong?
Answer
B, at distance , must be finalized first, and it improves A to .
Full solution
Only the smallest tentative distance can be finalized. A route through a closer vertex may still improve the others.
Frequently asked questions
What does Dijkstra's algorithm compute?
The shortest distance from one starting vertex to every other vertex in a graph with nonnegative edge weights, along with a shortest path to each.
How does it work?
Give the start distance 0 and every other vertex ∞. Repeatedly pick the unfinished vertex with the smallest distance, mark it final, and lower its neighbors' distances when a route through it is shorter.
Why must the weights be nonnegative?
The algorithm assumes the closest unfinished vertex cannot be reached more cheaply later. A negative edge could make a later route cheaper, so a finalized distance might be wrong.
How do you find the path itself?
Each time a vertex's distance improves, record the vertex it came from. Following these records back from the target gives the path.
Is a minimum spanning tree the same as a shortest path tree?
No. A minimum spanning tree minimizes the total weight of all its edges; a shortest path tree minimizes the distance from one start to each vertex. They can differ.