Optimisation algorithms study guide

What a trace is testing

A Dijkstra trace tests whether you can follow changing distance values and justify why a particular vertex is considered next. The important distinction is between a tentative distance and a distance that has been established by the algorithm. A tentative value is the best route currently known. It may later be reduced when another route is considered. Once the algorithm selects the smallest available tentative distance, that vertex is treated as having its shortest distance established for the trace.

A reliable reasoning method

First identify the start vertex and assign it distance 0; assign the other vertices unknown or infinite distances. At each stage, identify the unprocessed vertex with the smallest tentative value. Examine its available connections one at a time and calculate the possible new distance as the current distance plus the relevant edge weight. Compare this calculated value with the neighbour’s existing tentative value. Keep the smaller value and record the preceding vertex if the question requires the route as well as its length. Continue until the required destination has been established or the graph has been fully considered.

For example, in the graph from the revision note, the direct connection from S to A has weight 4, but the route S–B–A has length 1 + 2 = 3. Therefore, a trace must replace the earlier value 4 with 3. This demonstrates why a shortest-path question cannot be answered by selecting the smallest edge in isolation. Continuing the comparisons produces S–B–A–C–D with length 1 + 2 + 1 + 3 = 7.

Applying the result

When asked for a shortest path, distinguish between the numerical distance and the sequence of vertices. The distance is the sum of the weights; the path is the ordered list of vertices that produces that sum. In an application, the vertices might represent locations or points in a communication network, while weighted edges represent the measurable cost of travelling between them. The algorithm can then support choosing an efficient route.

Self-check questions

1. Which vertex is selected next, and what evidence from the tentative distances supports that choice?
2. When a new route is calculated, is its total smaller than the neighbour’s current value?
3. Have all relevant edge weights been added, rather than only the final edge?
4. Can you state both the shortest distance and the sequence of vertices?
5. Can you explain why a route with a larger first edge might still be shorter overall?

A strong answer should show the changing labels or distances clearly, explain each improvement, and avoid claiming that an unselected tentative value is final.