The University of Hong Kong · FACULTY OF MATHEMATICS

DASE7034 Chap.9 Shortest Paths and Dijkstra's Algorithm

- one subject, every graph, every model, every mark
5 Chapters3-page Bible
Our own words - no uploaded lecturer files
Updated for this semester
Chapter 9 of 12 · DASE7034

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.

In this chapter

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

Q [5 marks]. Marks shown in this routing drill are for AskSia practice, not the University's marking scheme. Permanent node u has distance 7, arc u to v costs 4 and v currently has label 13.
Dijkstra labels each node with the best distance currently known.Dijkstra labels each node with the best distance currently known. The smallest tentative label becomes permanent, then its outbound arcs offer improvements to neighbouring labels.s:0a:4b:2c:5t:8
Dijkstra labels each node with the best distance currently known. The smallest tentative label becomes permanent, then its outbound arcs offer improvements to neighbouring labels.
  • 2Compute candidate distance 7 plus 4.
  • 1Compare candidate 11 with current 13.
  • 2Update distance and predecessor together.
The candidate label is 11, which improves 13. Set the tentative distance of v to 11 and its predecessor to u. Do not make v permanent until it is the smallest tentative label among all remaining nodes. These marks are an AskSia practice allocation and do not reproduce an official University marking scheme.
Sia tip — Whenever a distance changes, change its predecessor on the same line.
Glossary

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.
FAQ

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.

Study strategy

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.

A+Everything unlocked
Unlocks this Bible + all 52 of your subjects at The University of Hong Kong, plus 1,000+ more Bibles across the AskSia library.
Sia - your DASE7034 tutor, unlimited, worked the way the exam marks it
The full 3-page Bible + practice bank with worked solutions
Chrome extension - sync your LMS so Sia knows your deadlines
Bilingual EN / Chinese on every Bible and every Sia answer
$0.99 Trial
30-day money-back · cancel in one tap · how it works