Routes Depend on What You Measure
A transport network can be represented by a graph whose edges carry numerical costs. If the cost records travel time, a recommended route minimizes time; if it records tolls, it minimizes toll. These objectives need not select the same route. The graph describes which movements are possible, while the weights encode which objective is being optimized.
Unless stated otherwise, graphs in this tutorial are finite and simple. The examples use undirected edges, so travel is possible in either direction. A one-way transport connection can instead be represented by a directed edge, or arc, with a weight assigned to that direction. A path is a sequence of distinct vertices in which consecutive vertices are joined by an edge (or, in a directed graph, by an arc in the stated direction).
The weight can represent time, distance, toll, fuel use, or another quantity that adds along a route. The interpretation must be fixed before comparing paths. For example, minimizing travel time does not automatically minimize toll, and combining these into one score requires an explicit rule for how they are traded off.
Dijkstra’s Algorithm for Nonnegative Weights
When every edge weight is nonnegative, Dijkstra’s algorithm finds shortest-path weights from a chosen source \(s\). A tentative label \(d(v)\) is the best route weight to \(v\) found so far; a predecessor records the previous vertex on that route. Initially \(d(s)=0\), and \(d(v)=\infty\) for every other vertex. At each step, choose an unsettled vertex with the smallest finite label and settle it. For each edge from that vertex \(u\) to a vertex \(v\) that is still unsettled, compare \(d(u)+w(uv)\) with \(d(v)\); if the former is smaller, replace \(d(v)\) by it and record \(u\) as predecessor.
Set the source label to zero, all other labels to infinity, and mark all vertices unsettled.
Settle an unsettled vertex of smallest finite label. If no unsettled vertex has a finite label, stop; the remaining vertices are unreachable from the source.
For each edge from the selected vertex to an unsettled neighbor, replace the neighbor’s label and predecessor only if the route through the selected vertex has smaller weight.
A settled label is the shortest-path weight. Follow predecessors backward from the destination to recover a route.
Proof. First, every finite tentative label is the weight of an actual path from \(s\): this holds at initialization for \(s\), and every update extends a previously recorded path by one edge. Thus a label cannot be smaller than the true minimum path weight to its vertex.
We prove that each vertex is settled with its correct label. Suppose the vertices settled so far have correct labels, and let \(u\) be the next vertex selected, with label \(d(u)\). If \(u=s\), its label is zero, which is correct because edge weights are nonnegative. Otherwise, take a minimum-weight path from \(s\) to \(u\). Such a path exists when \(u\) is reachable: with nonnegative weights, removing any repeated-vertex section does not increase the weight, so a minimum can be found among the finitely many paths with distinct vertices.
Along this path, let \(x\) be the first unsettled vertex, and let \(y\) be the vertex immediately before \(x\). The vertex \(y\) is settled (or is \(s\)), so its label is correct. When \(y\) was settled, the algorithm considered the edge \(yx\); hence the current label of \(x\) is at most the weight of the path prefix from \(s\) to \(x\). The rest of the chosen path from \(x\) to \(u\) has nonnegative weight, so that prefix weighs at most the full path to \(u\). Since \(u\) was selected with a smallest unsettled label, \(d(u)\le d(x)\). Combining these inequalities shows that \(d(u)\) is at most the minimum path weight to \(u\). The first paragraph shows it is at least that minimum, so equality holds.
This proves the claim for every settled vertex by induction on the number of settled vertices. Finally, if the algorithm stops with no finite unsettled label, but some unsettled vertex were reachable, a path from \(s\) to it would contain a first unsettled vertex after a settled one. Relaxing the edge between them would have given that first unsettled vertex a finite label, a contradiction. Therefore all remaining vertices are unreachable. \(\square\)
Worked Route Calculations
Worked Example: Minimize Travel Time
Let \(V=\{s,a,b,c,t\}\) and let the undirected edge set be \(E=\{sa,sb,ab,ac,bc,at,ct,bt\}\). Assign travel-time weights \(w(sa)=4\), \(w(sb)=2\), \(w(ab)=1\), \(w(ac)=5\), \(w(bc)=3\), \(w(at)=10\), \(w(ct)=2\), and \(w(bt)=9\). Find a minimum-time route from \(s\) to \(t\).
Start with \(d(s)=0\) and \(d(a)=d(b)=d(c)=d(t)=\infty\). Settling \(s\) gives \(d(a)=0+4=4\) and \(d(b)=0+2=2\). Settling \(b\), whose label \(2\) is now smallest, gives \(d(a)=\min(4,2+1)=3\), \(d(c)=0+2+3=5\), and \(d(t)=0+2+9=11\). Settling \(a\), with label \(3\), offers \(3+5=8\) for \(c\), which does not improve \(5\). Settling \(c\), with label \(5\), offers \(5+2=7\) for \(t\), improving \(11\).
| Action | Settled | Labels after the action \((s,a,b,c,t)\) |
|---|---|---|
| Initialize | — | \((0,\infty,\infty,\infty,\infty)\) |
| Settle \(s\) | \(s\) | \((0,4,2,\infty,\infty)\) |
| Settle \(b\) | \(s,b\) | \((0,3,2,5,11)\) |
| Settle \(a\) | \(s,b,a\) | \((0,3,2,5,11)\) |
| Settle \(c\) | \(s,b,a,c\) | \((0,3,2,5,7)\) |
| Settle \(t\) | \(s,b,a,c,t\) | \((0,3,2,5,7)\) |
The predecessors of \(t,c,b\) are \(c,b,s\), respectively, so the route is \(s,b,c,t\). Its time is \(w(sb)+w(bc)+w(ct)=2+3+2=7\). Check: the theorem applies because each listed weight is nonnegative. The computed route has weight \(7\), equal to the settled label \(d(t)=5+2=7\).
Worked Example: Minimize Toll Instead
Keep \(V=\{s,a,b,c,t\}\) and \(E=\{sa,sb,ab,ac,bc,at,ct,bt\}\), but use toll weights \(w(sa)=1\), \(w(sb)=5\), \(w(ab)=1\), \(w(ac)=2\), \(w(bc)=1\), \(w(at)=10\), \(w(ct)=2\), and \(w(bt)=2\). Apply Dijkstra’s algorithm from \(s\).
Initially \(d(s)=0\) and the other labels are infinity. Settling \(s\) gives \(d(a)=0+1=1\) and \(d(b)=0+5=5\). Settling \(a\) gives \(d(b)=\min(5,1+1)=2\), \(d(c)=1+2=3\), and \(d(t)=1+10=11\). Settling \(b\) gives a candidate \(2+1=3\) for \(c\), which ties its current label, and a candidate \(2+2=4\) for \(t\), improving \(11\). Settling \(c\) gives \(3+2=5\) for \(t\), which does not improve \(4\).
| Action | Settled | Labels after the action \((s,a,b,c,t)\) |
|---|---|---|
| Initialize | — | \((0,\infty,\infty,\infty,\infty)\) |
| Settle \(s\) | \(s\) | \((0,1,5,\infty,\infty)\) |
| Settle \(a\) | \(s,a\) | \((0,1,2,3,11)\) |
| Settle \(b\) | \(s,a,b\) | \((0,1,2,3,4)\) |
| Settle \(c\) | \(s,a,b,c\) | \((0,1,2,3,4)\) |
| Settle \(t\) | \(s,a,b,c,t\) | \((0,1,2,3,4)\) |
The predecessor chain gives \(s,a,b,t\), with total toll \(w(sa)+w(ab)+w(bt)=1+1+2=4\). Check: under the travel-time weights from the preceding example, the route \(s,b,c,t\) cost \(2+3+2=7\), while this toll-minimizing route \(s,a,b,t\) has travel time \(4+1+9=14\). Thus the route with the least toll need not have the least travel time.
Worked Example: A Changed Edge Weight Changes the Route
Return to \(V=\{s,a,b,c,t\}\) and \(E=\{sa,sb,ab,ac,bc,at,ct,bt\}\) with the original travel-time weights, except increase \(w(bc)\) from \(3\) to \(10\). Run the algorithm again from \(s\).
Settling \(s\) gives \(d(a)=0+4=4\) and \(d(b)=0+2=2\). Settling \(b\) gives \(d(a)=\min(4,2+1)=3\), \(d(c)=2+10=12\), and \(d(t)=2+9=11\). Settling \(a\) improves \(c\) to \(3+5=8\); its route to \(t\) would have weight \(3+10=13\), so \(d(t)\) stays \(11\). Settling \(c\) improves \(t\) to \(8+2=10\).
| Action | Settled | Labels after the action \((s,a,b,c,t)\) |
|---|---|---|
| Initialize | — | \((0,\infty,\infty,\infty,\infty)\) |
| Settle \(s\) | \(s\) | \((0,4,2,\infty,\infty)\) |
| Settle \(b\) | \(s,b\) | \((0,3,2,12,11)\) |
| Settle \(a\) | \(s,b,a\) | \((0,3,2,8,11)\) |
| Settle \(c\) | \(s,b,a,c\) | \((0,3,2,8,10)\) |
| Settle \(t\) | \(s,b,a,c,t\) | \((0,3,2,8,10)\) |
The new predecessor chain gives \(s,b,a,c,t\), with weight \(2+1+5+2=10\). The former route \(s,b,c,t\) now weighs \(2+10+2=14\). Also, the route \(s,a,c,t\) weighs \(4+5+2=11\), and \(s,b,t\) weighs \(2+9=11\). Check: the algorithm’s label is \(d(t)=8+2=10\), and its route is strictly cheaper than these alternatives. The edge-weight change therefore changes the recommended route.
Why the Nonnegative-Weight Condition Matters
Dijkstra’s algorithm relies on the fact that extending a route cannot reduce its weight. A negative edge can violate that fact: a route through a vertex already settled might later become cheaper by first reaching a different vertex. The algorithm then may stop with an incorrect destination label.
Common pitfall: using Dijkstra with a negative weight. Consider the directed graph \(V=\{s,a,b,t\}\) with arcs \(E=\{(s,a),(s,b),(b,a),(a,t),(b,t)\}\) and weights \(w(s,a)=2\), \(w(s,b)=5\), \(w(b,a)=-4\), \(w(a,t)=2\), and \(w(b,t)=10\). A mistaken use of Dijkstra settles \(a\) at label \(2\), then gives \(t\) label \(2+2=4\). It next settles \(t\), since \(4<5\), and stops with the alleged answer \(4\). But the route \(s,b,a,t\) has weight \(5+(-4)+2=3\), so the alleged answer is wrong. This directed graph has no directed cycle, so the example does not rely on an endlessly decreasing cycle; the failure is the algorithm’s invalid assumption that a settled label cannot later improve.
In applications, choose the weight that matches the decision being made, check that the weights satisfy the algorithm’s hypotheses, and interpret the output in those terms. If several objectives matter, compute routes for each objective separately unless a specific combined cost has been defined. A change in traffic, tolls, or operating conditions can change edge weights and therefore change which route is best.
Check Your Understanding
Use the definitions and algorithm above to answer the following.
- In the first worked example, what is the weight of the route \(s,a,c,t\), and how does it compare with the minimum-time route?
- Why does the proof of Dijkstra’s algorithm require nonnegative weights on the remaining portion of a shortest path?
- In the toll example, which predecessor update first gives \(t\) its final label?
- After the change \(w(bc)=10\), recompute the weight of \(s,b,c,t\) and compare it with the selected route.
- Give an example of two different objectives for the same transport network and explain why they may recommend different routes.