Dijkstra's shortest-path algorithm
Dijkstra's algorithm finds shortest paths from one source in a weighted graph with non‑negative edge weights; engineers use it in routing, networking, and many optimization tasks.
Drafted with Aria, reviewed by the AiCanCode.org team · Updated . How we write and check our notes. Spotted an error? Use Give Feedback at the bottom of the page.
Why it matters
Dijkstra's algorithm is used by engineers to compute the shortest path from one start node to all other nodes in a network. Practical uses include route planning (network routers, maps), scheduling, and any system that needs fastest/cheapest routes on a weighted graph with non‑negative edges.
Key ideas
Start with simple definitions so the algorithm is clear.
- Graph: a pair G = (V, E) where V is a set of vertices (also called nodes) and E is a set of edges (ordered pairs for a directed graph, unordered pairs for undirected). I will use directed graphs, but the algorithm works for undirected graphs by treating each undirected edge as two opposite directed edges.
- Weight: a real number w(u, v) assigned to edge (u, v). The algorithm requires non‑negative weights, meaning for every edge (u, v), w(u, v) ≥ 0.
- Path: a sequence of vertices v0, v1, ..., vk such that each (vi, vi+1) is an edge. The length of a path is the sum of the weights of its edges.
- Shortest path from s to v is a path from s to v whose length is minimal among all s→v paths.
- Source: the chosen start vertex s from which we compute distances to all vertices.
- Tentative distance (often called dist[v]): the currently known shortest distance from s to v (may be updated during the run); initially dist[s] = 0 and dist[v] = ∞ for v ≠ s.
- Predecessor (pred[v]): the previous node on the current shortest known path from s to v; used to reconstruct the path.
- Settled (visited) set: the set of vertices whose final shortest distance from s has been determined. Once a vertex is settled, its distance does not change later (this is true only if weights are non‑negative).
- Relaxation: the operation of checking an edge (u, v) and updating dist[v] if going through u gives a shorter path: if dist[v] > dist[u] + w(u, v) then set dist[v] := dist[u] + w(u, v) and pred[v] := u.
- Priority queue: an abstract data structure that supports extracting the vertex with minimum tentative distance (extract‑min) and decreasing a key (decrease‑key). Implementations affect time complexity.
Exact statement (theorem-like): Dijkstra's algorithm, when run on a directed or undirected graph G = (V, E) with non‑negative edge weights w(e) ≥ 0 and a source s ∈ V, correctly computes for every v ∈ V the shortest path distance d(s, v) and a corresponding predecessor tree. Assumptions: no negative weights. If negative weights exist (even without negative cycles) correctness is not guaranteed. Vertices unreachable from s remain with dist[v] = ∞ and pred[v] = NIL.
Correctness idea (standard induction proof sketch asked in exams):
- Initialization: dist[s] = 0, dist[v] = ∞ for v ≠ s. The settled set S = {}.
- Greedy choice: at each step pick a vertex u not in S with smallest tentative dist[u] and add it to S.
- Claim: when u is added to S, dist[u] equals the true shortest distance d(s, u). Proof by contradiction / induction:
- Base: first vertex is s, dist[s] = 0 which is correct.
- Inductive step: assume for every x ∈ S the dist[x] is final. Let u be the newly chosen vertex of minimum tentative distance among V\S. Suppose there exists a path P from s to u with length < dist[u]. Let y be the first vertex along P that is not in S and let x be its predecessor on P (so x ∈ S). Because edges have non‑negative weights, the length of the prefix from s to x is ≥ d(s, x) = dist[x]. Then the path s→...→x→y gives dist[y] ≤ dist[x] + w(x, y). As dist[u] was minimum among V\S, dist[u] ≤ dist[y]. Following the remainder of P from y to u has non‑negative length, so the total path length to u via y is ≥ dist[y] ≥ dist[u], contradiction. Therefore dist[u] is final.
- The relaxation step ensures all neighbors' tentative distances are updated; repeating until all vertices are settled yields final distances.
What to draw for an exam diagram: draw a small directed graph with labelled vertices (circle with name inside) and arrows for directed edges. Label each arrow with its weight (a non‑negative number). To illustrate one Dijkstra step, draw a table with columns: Vertex | dist | pred | settled? and next to the graph show the chosen vertex bolded.
Formulas
dist[s] = 0 — dist is the shortest‑path distance from source s to itself (same units as the edge weights).
dist[v] = min over all paths P from s to v of sum_{(i->j) in P} w(i,j) — defines shortest path distance; weight unit (e.g. seconds, metres, cost units) applies.
relax(u, v): if dist[v] > dist[u] + w(u, v) then dist[v] := dist[u] + w(u, v); pred[v] := u; if using a priority queue, perform DecreaseKey on v's key in Q — operation used in algorithm.
Pseudocode syntax to remember (concise):
Dijkstra(G, w, s):
for each v in V: dist[v] := ∞; pred[v] := NIL
dist[s] := 0
Q := all vertices with their dist as key (priority queue)
while Q not empty:
u := ExtractMin(Q)
for each v that is a neighbor of u:
if dist[v] > dist[u] + w(u, v):
dist[v] := dist[u] + w(u, v); pred[v] := u
DecreaseKey(Q, v, dist[v])
Complexities to remember (depending on implementation):
O(V^2) — when using a simple array to find min dist (good for dense graphs).
O((E + V) log V) — when using a binary heap (priority queue) for ExtractMin and DecreaseKey (common practical choice).
O(E + V log V) — when using a Fibonacci heap (theoretical improvement).
(Here V = |V|, E = |E|; units: algorithmic time complexity, not physical units.)
Worked examples
Example 1 — standard step-by-step trace (university exam style) Graph (directed). Draw six vertices: S, A, B, D, C, E (circles labelled). Draw and label directed edges with weights as below (write them on the arrows): S -> A : 10 S -> B : 3 B -> A : 4 A -> C : 2 B -> C : 8 B -> D : 2 D -> C : 1 C -> E : 3 D -> E : 6
Goal: compute shortest distances from S. Initial table (write as three columns: Vertex | dist | pred): S | 0 | NIL A | ∞ | NIL B | ∞ | NIL C | ∞ | NIL D | ∞ | NIL E | ∞ | NIL
Step 0: set dist[S]=0; relax S's edges: A := 10 (pred A = S), B := 3 (pred B = S). Choose min dist among unvisited: B (3). Settle B. Relax edges from B:
- B->A: dist[A] = min(10, 3 + 4) = 7 → update pred[A]=B
- B->C: dist[C] = min(∞, 3 + 8) = 11 → pred[C]=B
- B->D: dist[D] = min(∞, 3 + 2) = 5 → pred[D]=B Table now: S 0 NIL (settled) A 7 B B 3 S (settled) C 11 B D 5 B E ∞
Choose min dist unvisited: D (5). Settle D. Relax from D:
- D->C: dist[C] = min(11, 5 + 1) = 6 → pred[C]=D
- D->E: dist[E] = min(∞, 5 + 6) = 11 → pred[E]=D Table: A 7 B C 6 D D 5 B (settled) E 11 D
Choose min unvisited: C (6). Settle C. Relax C->E: dist[E] = min(11, 6 + 3) = 9 → pred[E]=C Table: A 7 B E 9 C
Choose min unvisited: A (7). Settle A. Relax A->C: potential dist[C] = 7 + 2 = 9 which is > 6, so no change. Choose next: E (9). Settle E. No improvements. Final shortest distances (bold the answers):
- dist[S] = 0
- dist[B] = 3 via S -> B
- dist[A] = 7 via S -> B -> A
- dist[D] = 5 via S -> B -> D
- dist[C] = 6 via S -> B -> D -> C
- dist[E] = 9 via S -> B -> D -> C -> E (Answer: shortest path to E is S->B->D->C->E with total weight 9.)
Example 2 — show failure with negative edge (why non‑negative requirement matters) Graph: vertices S, A, B, C. Edges: S->A : 2 S->B : 5 B->C : -10 C->A : 2 There is no negative cycle. True shortest path S→A is via S->B->C->A: 5 + (-10) + 2 = -3. Dijkstra's run (greedy): initial dist[A]=2, dist[B]=5. The algorithm picks A first (dist 2) and settles it permanently as 2. The better path of length -3 is found only after settling A, so Dijkstra will output dist[A] = 2 (wrong). Conclusion: Dijkstra can give incorrect answers when negative-weight edges exist. Always require non‑negative weights.
Common mistakes
- Confusing settled (finalized) with merely visited; once settled, a node's distance should not be changed (if weights are non‑negative).
- Reporting complexity incorrectly: say O(E log V) without adding the V log V term (give O((E + V) log V) or explain why constants differ by implementation).
- When tracing by hand, mis‑picking the next vertex with minimum tentative distance (do not pick any arbitrary small value; pick the global min among unvisited).
- For undirected graphs: forgetting to treat an undirected edge as two directed edges or missing relaxation in the opposite direction.
For your exam
Typical question types:
- Definitions and short notes: define relaxation, priority queue, and give correctness condition (non‑negative weights).
- Derivation/Proof: prove correctness of Dijkstra by induction (explain the greedy choice and why settled distances are final).
- Numerical trace: given a small graph, perform Dijkstra and show the dist and pred tables after each step; draw the graph and highlight chosen vertices.
- Complexity questions: compare array vs heap implementations and give time complexity.
- Program/Algorithm writing: give clear pseudocode and explain data structures used. What a full‑marks answer includes:
- Precise definitions of terms (already bolded in Key ideas). State the non‑negative weight assumption.
- Correct pseudocode with initialization, ExtractMin loop, and relaxation, and clear explanation of the priority queue operations used.
- A correctness proof by induction or by contradiction that uses the fact that weights are non‑negative.
- A trace for small graphs showing each step (table of dist, pred, and settled set) and final shortest paths.
- Correct statement of time complexity for the chosen implementation and justification (counts of ExtractMin and DecreaseKey operations).
Quick check
- What condition on edge weights is required for Dijkstra's algorithm to be guaranteed correct?
- Write the relaxation rule for edge (u, v).
- State the typical time complexity when using a binary heap for the priority queue. Answers: 1) All edge weights must be non‑negative (w(u,v) ≥ 0). 2) If dist[v] > dist[u] + w(u, v) then dist[v] := dist[u] + w(u, v) and pred[v] := u. 3) O((E + V) log V).
Finished this topic? Mark it so your progress, study plan and readiness keep up.
Stuck on something here?