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.

  1. Give the start distance 00 and every other vertex distance ∞\infty.
  2. Pick the unfinished vertex with the smallest distance. Mark it final.
  3. 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.
  4. Repeat until every vertex is final.
A weighted network and its shortest route from S to T Six vertices S, A, B, C, D and T with nine weighted edges: S–A 4, S–B 2, A–B 1, A–C 5, B–C 8, B–D 10, C–D 2, C–T 6 and D–T 3. The shortest route from S to T, S–B–A–C–D–T with total 13, is highlighted. 4 2 1 5 8 10 2 6 3 S A B C D T
A weighted network and its shortest route from S to T

Why the closest vertex can be finalized

Suppose uu is the unfinished vertex with the smallest tentative distance. Any other route to uu must leave the finished region through some unfinished vertex ww, and ww is already at least as far as uu. With no negative edges, the rest of that route can only add length, so nothing beats uu‘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

  1. In the figure, what is the shortest distance from S to C?

    Answer

    88

    Full solution

    S–B–A–C: 2+1+52 + 1 + 5. The edge B–C gives 2+8=102 + 8 = 10.

  2. In the figure, the weight of C–D changes to 55. What is the new distance from S to T?

    Answer

    1414

    Full solution

    D is now reached via B for 1212, and T via C for 8+6=148 + 6 = 14, less than 12+3=1512 + 3 = 15.

  3. Find the shortest distances from T to every other vertex in the figure.

    Answer

    D 33, C 55, A 1010, B 1111, S 1313

    Full solution

    The edges have no direction, so the path from T to S reverses S–B–A–C–D–T.

  4. 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: 0,2,3,8,10,130, 2, 3, 8, 10, 13.

  5. Triangle X, Y, Z has edges X–Y 77, X–Z 33 and Z–Y 22. Find the shortest distance from X to Y.

    Answer

    55

    Full solution

    X–Z–Y costs 3+23 + 2, less than the direct edge.

  6. The predecessor records in Example 1 form a tree. How many edges does it have?

    Answer

    55

    Full solution

    Each of the 55 vertices other than S has one predecessor, and a tree on 66 vertices has 55 edges.

  7. Can the shortest path from S to T use an edge of weight 1010 in the figure?

    Answer

    No

    Full solution

    B–D gives D the distance 1212, but the route through C gives 1010, and the shortest route to T does not pass through B–D.

  8. A student marks A final at distance 44 right after leaving S. What is wrong?

    Answer

    B, at distance 22, must be finalized first, and it improves A to 33.

    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.