DASE7034 Chap.9 Shortest Paths and Dijkstra's Algorithm
Shortest Paths and Dijkstra's Algorithm
Shortest-path models minimise additive arc cost. Dijkstra's algorithm applies when every arc cost is nonnegative: the smallest tentative label becomes permanent, its outbound arcs are relaxed and predecessor labels record the route.
Distance and path are separate outputs, so the final answer needs both the permanent value and a backtrack through predecessors.
Define the network and cost meaning
Represent locations or states as nodes and permitted transitions as directed or undirected arcs. Attach an additive cost such as distance, time or money to each arc, keeping units consistent.
Direction matters: a one-way connection or asymmetric travel time requires separate directed arcs. The problem asks for a path from a specified source to a destination with minimum total arc cost.
If several criteria matter, they cannot be added until a defensible common scale or priority rule is stated.
Maintain tentative labels correctly
Set the source distance to zero and every other tentative distance to infinity. Repeatedly choose the unsettled node with the smallest tentative label and make it permanent. For each outgoing arc, form a candidate equal to the permanent label plus the arc cost.
If the candidate is smaller than the neighbour's current label, replace the label and record the current node as predecessor. A tentative label is provisional; it becomes final only when selected as the smallest unsettled value.
Check the nonnegative-cost assumption
Dijkstra's permanence argument relies on every arc cost being nonnegative.
A later route cannot reduce a permanent label when extending paths only adds nonnegative amounts. With a negative arc, that reasoning fails and another algorithm is required; with a reachable negative cycle, no finite shortest path exists for affected destinations. Zero-cost arcs are allowed, although ties need consistent handling.
State the cost assumption before using the algorithm rather than treating it as a hidden technicality.
Recover and verify the route
The destination label gives the minimum value but not the sequence of nodes. Follow predecessor pointers backward from the destination to the source, then reverse the list. Re-add the costs on those arcs and confirm that the sum equals the permanent destination label.
If the destination remains infinite, it is unreachable from the source. When several predecessors yield the same label, multiple shortest routes may exist; report one valid route and note the tie if it matters operationally.
What this chapter covers
- 01
Shortest-path variants
- 02
Tentative and permanent labels
- 03
Outbound arc relaxation
- 04
Predecessor backtracking
- 05
Nonnegative-cost condition
Worked example · free
Relax one outgoing arc
- 2Compute candidate distance 7 plus 4.
- 1Compare candidate 11 with current 13.
- 2Update distance and predecessor together.
Key terms
- Tentative Label
- The best source-to-node distance known so far for a node not yet made permanent.
- Permanent Label
- A shortest-path distance fixed by Dijkstra's selection rule under nonnegative arc costs.
- Predecessor
- The preceding node recorded when a label improves, used to reconstruct the path.
Shortest Paths and Dijkstra's Algorithm FAQ
Why must arc costs be nonnegative for Dijkstra?
A later path containing a negative arc could undercut a node already declared permanent. Nonnegative costs guarantee that extending paths through unselected nodes cannot reduce the current smallest tentative label.
How is the actual route recovered?
Start at the destination and repeatedly follow its predecessor until the source is reached, then reverse the sequence. Re-add the listed arc costs to verify that the route matches the permanent distance.
What if two candidate routes tie?
Either predecessor can produce a shortest path if both give the same minimum label. Record alternatives if the question requires every shortest route; otherwise use a consistent tie rule and report one valid path.
Exam move
Draw a label table with distance, predecessor and status for every node. Update only from the newly permanent node's outbound arcs. When the destination becomes permanent, stop the forward calculation, backtrack the route and re-add every arc cost. Before running the algorithm, list every arc with direction, cost and unit, then scan for negative values. Initialise the source at zero and all other nodes at infinity.
In each iteration, circle the smallest unsettled label, mark it permanent and show every candidate relaxation from that node, retaining the old label when the candidate is not smaller. Record the predecessor only when a label improves. Treat ties consistently and do not declare a tentative destination final merely because it has been reached.
After permanence, reconstruct the route backward through predecessors, reverse the list and add its arc costs independently. The sum must equal the destination label. If a node remains at infinity, state that it is unreachable from the selected source. Repeat one example after changing a single arc direction, because this reveals how easily an apparently small network edit changes both reachability and the shortest route.
Working through Shortest Paths and Dijkstra's Algorithm in DASE7034? Sia is AskSia’s AI Mathematics tutor — ask any DASE7034 Shortest Paths and Dijkstra's Algorithm question and get a clear, step-by-step explanation grounded in how DASE7034 is taught and assessed. Read this chapter free, then take your hardest questions to Sia.