6.3.1 Relaxation and Dijkstra's algorithm

0 · Recall Warm-up

Answer from memory first. Answers are in the Answer Vault at the bottom.

Prim's key[v] holds? from Lesson 6.2.3
BFS solves shortest paths when? from Lesson 6.1.1
Binary heap insert and extract cost? from Lesson 0.2.2

1 · The Hook

🎣

Maps apps need the cheapest route when roads have different lengths, so BFS (which counts edges) is not enough. Dijkstra's algorithm is Prim with one change: a vertex's key is the length of the best known path from the source, not of one edge. It is the most asked graph algorithm in GATE.

2 · Predict First

🤔

Six towns, road lengths as given. What is the shortest distance from A to D?

Make a guess in your head. The answer opens Section 3.

3 · Core Concept

💡

Predict First — the answer

A–C–B–D = 2 + 1 + 5 = 8 (A–B–D is 9, A–C–D is 10).

Relaxation

dist[v] is the best path length known so far (∞ at the start, 0 for the source).

RELAX(u, v): if dist[u] + w(u, v) < dist[v]:
                 dist[v] = dist[u] + w(u, v); parent[v] = u

Every single-source shortest-path algorithm is relaxation in some order.

Dijkstra (non-negative weights only)

dist[s] = 0; all others ∞
repeat V times:
    u = the unfinished vertex with the smallest dist     // finalise it
    for each edge u → v: RELAX(u, v)

Once a vertex is finalised its distance never changes: any other route would pass through an unfinished vertex that is already at least as far, and with non-negative weights the rest of that route cannot make it cheaper.

Six-town trace from A

Finalise	dist A	B	C	D	E	F
start	0	∞	∞	∞	∞	∞
A (0)	·	4	2	∞	∞	∞
C (2)	·	3	·	10	12	∞
B (3)	·	·	·	8	12	∞
D (8)	·	·	·	·	10	14
E (10)	·	·	·	·	·	13
F (13)	·	·	·	·	·	·

Order A, C, B, D, E, F; distances B 3, C 2, D 8, E 10, F 13.

Why negative edges break it

Directed: A → B 2, A → C 3, C → B −2, B → D 1. Dijkstra finalises B at 2 and sets D = 3 through B. When C (3) is finalised, the edge C → B (−2) comes too late: B is already finished, so the saving never reaches D. Dijkstra reports dist[D] = 3, but A → C → B → D costs 2.

Cost

Priority structure	Time
Array	Θ(V²)
Binary heap	O((V + E) log V)
Fibonacci heap (named only)	O(E + V log V)

4 · Visual

Diagram: 4 · 2 · 1 · 5 · 8 · 10 · 2 · 6 · 3 · A 0 · B 3 · C 2 · D 8 · E 10 · F 13

Dijkstra from A: final distances inside the nodes, shortest-path tree in red. Here it happens to equal the MST; in general it does not.

5 · Worked Examples

Example 1 Easy

Dijkstra from C on the six-town graph: distance to F?

Solution

C–B–D–E–F = 1 + 5 + 2 + 3 = 11.

Example 2 Medium

Dijkstra from D on the six-town graph (ties by name): order of finalisation?

Solution

D 0; E 2; B 5 and F 5 (B first by name); C 6; A 8: D, E, B, F, C, A.

Example 3 GATE

Dijkstra with a binary heap on a graph with V = 1,000 and E = 5,000: order of the running time?

Solution

O((V + E) log V) ≈ 6,000 × 10 = about 60,000 basic steps.

6 · GATE Traps

⚠️

Dijkstra needs non-negative weights; a negative edge can give wrong answers even with no negative cycle.
Finalised in non-decreasing order of distance.
Prim's key = one edge; Dijkstra's key = whole path.
Shortest-path tree ≠ MST in general.

7 · Memory Hook

🧠

"Take the closest unfinished vertex; relax its edges."

8 · Connect the Dots

Dijkstra fails with negative edges. The next lesson's Bellman–Ford handles them (and detects negative cycles) by relaxing every edge V − 1 times; on a DAG one pass in topological order is enough.

9 · Self-Test

GATE format. Try every question before opening the vault.

Q1NAT1 markDijkstra

Dijkstra from A on the six-town graph: distance to F?

Numerical answer: ________

Q2NAT2 marksDijkstra

Dijkstra from F on the six-town graph: distance to C?

Numerical answer: ________

Q3MCQ1 markOrder

Dijkstra from A on the six-town graph finalises vertices in which order?

(A) A, B, C, D, E, F
(B) A, C, B, E, D, F
(C) A, C, B, D, E, F
(D) A, C, D, B, E, F

Q4NAT2 marksNegative edge

Directed graph A → B 2, A → C 3, C → B −2, B → D 1. What distance does Dijkstra from A report for D?

Numerical answer: ________

Q5MCQ1 markCost

Dijkstra with a binary heap and adjacency lists runs in:

(A) O(VE)
(B) O(V + E)
(C) O(V³)
(D) O((V + E) log V)

10 · Rule Card

Relax: dist[v] = min(dist[v], dist[u] + w).
Dijkstra: finalise the closest unfinished vertex; non-negative weights only.
Θ(V²) array; O((V + E) log V) binary heap; O(E + V log V) Fibonacci heap.
Shortest-path tree ≠ MST in general.

11 · Concept Ledger

Unlocked in this lesson. From here on, these terms may be used.

relaxationDijkstra's algorithmfinalised verticesnon-negative weight requirementDijkstra cost by priority structureshortest-path tree

12 · Answer Vault

Answer Vault

Try the questions first. Open when you are ready to check.

Recall Warm-up

The cheapest single edge from the tree to v.
Every edge has the same weight (unweighted).
O(log n) each.