Dijkstra: nonnegative weights and settled distances
Contract and connection
Reuse existing adjacency representations, BFS/DFS and heap operations. BFS minimizes edge count in an unweighted graph; it does not generally minimize arbitrary weighted path sums. Here a directed or undirected graph has nonnegative edge weights. A shortest-path distance δ(s,v) is the minimum sum of edge weights from source s to v, or ∞ if no path exists. Zero weights are allowed.
1. Tentative distances represent real paths
Initialize d[s]=0, other d[v]=∞, all parents absent. A relaxation of (u,v) with finite d[u] checks whether d[u]+w(u,v)<d[v]; if so update d[v] and parent[v]=u. Every finite d[v] is the length of a discovered source-to-v path, so it is an upper bound on the shortest distance. ∞ must be handled explicitly in code; adding to a sentinel can overflow.
Dijkstra repeatedly chooses an unsettled vertex u of minimum tentative distance. If that distance is ∞, stop: all remaining vertices are unreachable. Mark u settled and relax its outgoing edges toward unsettled vertices. With an indexed binary min-heap, updating a queued key uses decrease-key. The source need not be connected to every vertex.
2. Why settlement is final
Invariant: every settled vertex has its true shortest distance. Assume u is the next minimum and consider a shortest source-to-u path. Let y be its first unsettled vertex and x its settled predecessor, if u is not the source. When x was processed, relaxation made d[y] no larger than the path-prefix length to y. Nonnegative remaining edges imply that prefix is no larger than the full shortest distance to u. Minimum selection gives d[u]<=d[y]<=δ(s,u). Since d[u] is always an actual-path upper bound, d[u]>=δ(s,u), so equality holds. This is the exact place nonnegative weights are needed.
3. Worked trace with an improvement
Directed edges: s→a=4, s→b=1, b→a=2, a→t=1, b→t=7. Settle s, giving a=4,b=1,t=∞. Settle b, improving a=3,t=8. Settle a, improving t=4. Settle t. Final distances (s,b,a,t)=(0,1,3,4); parents b←s,a←b,t←a. Follow parents backward from t and reverse to recover s,b,a,t. The direct s→a edge is not in that shortest route.
Ties can be processed in any order; zero-weight edges and equal-distance alternatives can yield multiple shortest paths. Update parents only on a strict improvement in this simple implementation, and do not overwrite already settled vertices. This avoids gratuitous equal-distance parent rewrites and keeps a well-defined reconstruction tree.
4. A negative-edge counterexample
Edges s→a=2,s→b=5,b→a=−4. Ordinary Dijkstra settles a at 2 before b, but the true shortest distance to a is 1 via b. There is no negative cycle here: a single negative edge already invalidates the general proof. Some negative-edge inputs happen to work, but that is not a correctness guarantee. Use Bellman–Ford when appropriate, as in the next lesson.
5. Complexity depends on the queue
With an adjacency matrix and scanning V entries to choose each minimum, time O(V²), auxiliary arrays O(V), excluding graph storage. With adjacency lists and an indexed binary heap, O((V+E) log V) time and O(V) auxiliary queue/arrays, excluding O(V+E) graph storage. A common lazy heap instead pushes a new (distance,vertex) pair on each improvement; on pop, discard pairs whose distance no longer equals d[v], or vertices already settled. It can keep O(E+1) entries and has O(V+(E+1) log(E+2)) time for the reachable relaxations plus initialization; quote the implementation actually used rather than claiming decrease-key bounds automatically.
Early termination when a target is settled is safe; stopping when it is first discovered is not. Distances are path sums, while Prim's keys are single connecting-edge weights. A shortest-path tree need not minimize the sum of its own edge weights over all spanning trees.
Original practice: six single-correct MCQs
These original teaching questions are not previous-year questions. Choose exactly one answer.
P01. Dijkstra permits which weights under its standard guarantee?
A. Only strictly positive B. Nonnegative, including zero C. Any negative weights without cycles D. All real weights unconditionally
Answer: B
A: Zero weights are allowed.
B: Nonnegative suffixes support the settlement proof.
C: One negative edge can break it even without a cycle.
D: The proof needs a weight restriction.
P02. In the worked s,a,b,t graph, shortest distance to t?
A. 4 B. 5 C. 8 D. ∞
Answer: A
A: s→b→a→t costs 1+2+1=4.
B: Direct route through a costs 5 and is worse.
C: s→b→t costs 8 and is worse.
D: t is reachable.
P03. Safe early stopping for one target occurs when it is:
A. First discovered B. Settled as minimum tentative vertex C. First mentioned in adjacency list D. Given any finite parent
Answer: B
A: A later route can improve it.
B: The invariant then proves its distance final.
C: Mentioning does not determine distance.
D: Finite paths can be suboptimal.
P04. For s→a=2,s→b=5,b→a=−4, true shortest distance to a?
A. −4 B. 1 C. 2 D. 5
Answer: B
A: This omits the source-to-b cost.
B: 5−4=1 via b.
C: This is the direct edge, not the optimum.
D: This is distance to b.
P05. Indexed binary heap plus adjacency lists gives:
A. O(V+E) always B. O((V+E) log V) C. O(V²E) necessarily D. O(log V) total
Answer: B
A: Heap operations add logarithmic factors.
B: V extractions and up to E updates give this bound.
C: This is not the standard implementation bound.
D: Many vertices and edges must be processed.
P06. A finite tentative d[v] before settlement is:
A. Always below true distance B. A discovered-path upper bound C. Always final D. An MST connecting-edge weight
Answer: B
A: It is the length of an actual path.
B: The shortest path cannot be longer than a discovered one.
C: It may decrease before settlement.
D: That describes a Prim key, not d[v].
Sources and scope
Aligned to the 2026 course. This lesson covers the stated slice, not the entire Algorithms syllabus. All numerical examples and questions are original. No claim of 2027 completeness.
Sign in to keep your progress. Sign in