ACompressed recap
🧾
Relaxation dist[v] = min(dist[v], dist[u] + w). Dijkstra: closest unfinished vertex, non-negative weights, Θ(V²) array / O((V + E) log V) heap. Bellman–Ford: V − 1 rounds, Θ(VE), extra pass detects negative cycles. DAG: relax in topological order, Θ(V + E). Floyd–Warshall: k outermost, Θ(V³), negative cycle ⇔ D[i][i] < 0.
BMerged rule card
6.3.1 Relaxation and Dijkstra's algorithm
- 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.
6.3.2 Bellman–Ford, negative cycles, shortest paths in DAGs
- Bellman–Ford: V − 1 rounds relaxing all edges; extra pass detects negative cycles; Θ(VE).
- Round i fixes paths with ≤ i edges (DP on edge count).
- DAG: relax in topological order once; Θ(V + E); negative edges fine.
6.3.3 All-pairs shortest paths: Floyd–Warshall
- D⁽ᵏ⁾[i][j] = min(D⁽ᵏ⁻¹⁾[i][j], D⁽ᵏ⁻¹⁾[i][k] + D⁽ᵏ⁻¹⁾[k][j]); k outermost.
- Θ(V³) time, Θ(V²) space; negatives OK; negative cycle ⇔ D[i][i] < 0.
- Transitive closure: same loops on booleans.
CInterleaved GATE-style questions
Q1NAT1 markDijkstra
Dijkstra from A on the six-town graph: distance to E?
Numerical answer: ________
Q2NAT2 marksDijkstra
Dijkstra from D on the six-town graph: distance to A?
Numerical answer: ________
Q3MCQ1 markNegative edges
Dijkstra's algorithm is guaranteed correct when:
- (A) all edge weights are non-negative
- (B) the graph is undirected
- (C) the graph has no negative cycle
- (D) the graph is a DAG
Q4NAT2 marksBellman–Ford
In the lesson's Bellman–Ford example, final dist[x]?
Numerical answer: ________
Q5NAT1 markRounds
Bellman–Ford on 25 vertices performs how many relaxation rounds before its negative-cycle check?
Numerical answer: ________
Q6NAT2 marksDAG paths
In the lesson's DAG, shortest distance from s to x?
Numerical answer: ________
Q7NAT2 marksFloyd
In the lesson's Floyd–Warshall final matrix, D[4][3]?
Numerical answer: ________
Q8MSQ2 marksCosts
Match costs. Which are correct?
- (A) Floyd–Warshall Θ(V³)
- (B) DAG shortest paths Θ(V + E)
- (C) Bellman–Ford Θ(VE)
- (D) Dijkstra with an array Θ(E log V)
DAnswer Vault
Answer Vault
Try the questions first. Open when you are ready to check.
Q1 Answer: 101 mark
A–C–B–D–E = 2 + 1 + 5 + 2.
Re-read: Lesson 6.3.1 — Relaxation and Dijkstra's algorithm
Q2 Answer: 82 marks
D–B–C–A = 5 + 1 + 2.
Re-read: Lesson 6.3.1 — Relaxation and Dijkstra's algorithm
Q3 Answer: (A)1 mark
Negative edges can break it even without negative cycles.
- (B) is wrong: Irrelevant.
- (C) is wrong: Not enough.
- (D) is wrong: Use the DAG algorithm instead; Dijkstra may still fail with negative edges.
Re-read: Lesson 6.3.1 — Relaxation and Dijkstra's algorithm
Q4 Answer: 42 marks
s → y → x = 7 − 3.
Re-read: Lesson 6.3.2 — Bellman–Ford, negative cycles, shortest paths in DAGs
Q5 Answer: 241 mark
V − 1.
Re-read: Lesson 6.3.2 — Bellman–Ford, negative cycles, shortest paths in DAGs
Q6 Answer: 62 marks
s → x directly (s → t → x is 9).
Re-read: Lesson 6.3.2 — Bellman–Ford, negative cycles, shortest paths in DAGs
Q7 Answer: 72 marks
4 → 1 → 2 → 3 = 2 + 3 + 2.
Re-read: Lesson 6.3.3 — All-pairs shortest paths: Floyd–Warshall
Q8 Answer: (A) (B) (C)2 marks
The array version is Θ(V²).
- (D) is wrong: Θ(E log V) is the heap version.
Re-read: Lesson 6.3.3 — All-pairs shortest paths: Floyd–Warshall