Dijkstra's shortest path algorithm

Overview

Recall questions on what Dijkstra's shortest path algorithm solves, weighted graphs, the distance table and repeating step, a worked example, recovering the route, negative weights, unreachable nodes, time complexity, uses, and provisional versus final distances.

What you need to know

Answer each one before you reveal it.

Questions from this subtopic

Each one with the model answer underneath.

1. 1

   What problem does Dijkstra's algorithm solve?

   Model answer

   It finds the shortest, that is the lowest total weight, path from one starting node to every other node in a weighted graph, and therefore to any particular destination. The weights must not be negative.

2. 2

   Describe a weighted graph precisely enough for someone to draw one.

   Model answer

   A set of nodes, drawn as labelled circles, joined by edges drawn as lines. Each edge connects two nodes and carries a number, its weight, written beside it, representing a cost such as distance, time or price. In an undirected graph an edge can be travelled in either direction; in a directed graph each edge carries an arrow and may only be travelled that way.

3. 3

   What information does Dijkstra's algorithm keep while it runs?

   Model answer

   A table with one row per node holding the smallest total distance from the start found so far and the previous node on that best-known route, and a record of which nodes have been visited. Distances begin at zero for the start node and infinity for every other node, and no node begins as visited.

4. 4

   State the repeating step of Dijkstra's algorithm.

   Model answer

   From the unvisited nodes, choose the one with the smallest current distance. For each of its neighbours that is still unvisited, add the connecting edge's weight to the chosen node's distance; if that total is less than the neighbour's recorded distance, replace it and record the chosen node as the neighbour's previous node. Then mark the chosen node as visited and never revisit it. Repeat until the destination has been visited or no unvisited node is reachable.

5. 5

   Why can a node be marked visited and then never reconsidered?

   Model answer

   Because it is chosen as the unvisited node with the smallest distance, and every remaining route to it would have to pass through some other unvisited node whose distance is already at least as large. With no negative weights, adding a further edge can only increase the total, so no shorter route to it can still be found.

6. 6

   Take this graph. A joins B with weight 4 and C with weight 2. C joins B with weight 1, D with weight 8 and E with weight 10. B joins D with weight 5. D joins E with weight 2. Run Dijkstra's from A and give the shortest route to E.

   Model answer

   Start with A at 0 and the rest at infinity. Visit A: B becomes 4 via A, C becomes 2 via A. The smallest unvisited is C at 2. Visit C: B improves to 3 via C, D becomes 10 via C, E becomes 12 via C. The smallest unvisited is B at 3. Visit B: D improves to 8 via B. Visit D at 8: E improves to 10 via D. Visit E at 10, which is the destination. The shortest route is A to C to B to D to E with a total of 10.

Other ways to work this

The same content, four other ways.

What is inside Levo

Six ways to work the same material.