Skip to content
Menu
中文Sign in
← All questions

How do you reconstruct the shortest path from home to university after running Dijkstra's algorithm?

To reconstruct the shortest path, you follow the predecessor arrows backward from the destination vertex to the source vertex. During the algorithm's execution, whenever a vertex is selected or updated, an arrow is drawn from the vertex that supplied the current best label. Once the destination label is finalized, you start at the destination and repeatedly move to the predecessor indicated by the drawn arrow until you reach the source. In this example, the backward chain is university ← D ← A ← home, which gives the forward path home → A→DA \to D → university.

Conditions

  • Predecessor arrows must have been recorded during the label updates.
  • The destination label has been finalized (circled).
  • The graph is directed or treated as such for the purpose of following the recorded arrows.

Reasoning, step by step

  1. Start at the destination vertex (university).
  2. Identify the predecessor arrow pointing to university (from D).
  3. Move to vertex D.
  4. Identify the predecessor arrow pointing to D (from A).
  5. Move to vertex A.
  6. Identify the predecessor arrow pointing to A (from home).
  7. Move to the source vertex (home).
  8. Reverse the sequence to state the path in forward order: home → A→DA \to D → university.

Example

The video shows yellow highlighting tracing the route backward: "Working backwards from university, we've come from D ... following the arrow backwards from D, that's come from A ... and then following from A, that's come from home." The final path is written as home - A - D - university.

Common misconceptions

  • Assuming the path is found by following arrows forward from the source.
  • Forgetting to record predecessor arrows during the algorithm, making reconstruction impossible.
  • Confusing the shortest distance value with the actual sequence of vertices.

Watch the explanation

3:44 – 4:00Watch this moment ↗

Explore next

Answers are generated from source material and independently checked. Consult the original video or creator if something is unclear.