DSA, Database System & Operating System — Sorting, Searching, and Graphs, NEC licence examination syllabus (Nepal Engineering Council).
Shortest-Path Algorithm: Dijkstra's, revisited with full numerical depth
The same algorithm you met briefly in networking — now with the full step-by-step table format expected here.
Dijkstra's algorithm (a greedy approach) finds the shortest path from one source vertex to every other vertex in a graph with non-negative edge weights.
Worked example — Dijkstra from A on graph:
Edges: A-B(4), A-C(1), C-B(2), B-D(5), C-D(8)
Step 1: dist[A]=0, all else=∞. Visit A.
Step 2: Update B: min(∞, 0+4)=4. Update C: min(∞, 0+1)=1.
Step 3: Visit C (smallest unvisited=1). Update B: min(4, 1+2)=3.
Update D: min(∞, 1+8)=9.
Step 4: Visit B (smallest unvisited=3). Update D: min(9, 3+5)=8.
Step 5: Visit D (only one left, dist=8).
Final shortest distances from A: B=3, C=1, D=8
Notice how B's distance improved from 4 to 3 once C was processed — this "relaxation" (finding a shorter path through an intermediate vertex) is the entire engine driving Dijkstra's algorithm forward.
💡 Practice this exact table-tracking format — [visited vertices | current shortest distances to each vertex] updated after every step — on a 5-6 vertex weighted graph. This is graded step-by-step, not just on the final answer.
Why non-negative weights are required
The chapter notes the restriction. The reason is the algorithm's most examinable property, because it exposes exactly why the greedy approach works at all.
Dijkstra finalises a vertex the moment it becomes the nearest unvisited one, and never revisits it. That is sound only because every remaining path must be at least as long as the one just chosen — which holds precisely when no edge can reduce a distance. A negative edge breaks that assumption, so a vertex can be finalised at a distance that a later path improves on.
A counter-example: A→B costs 2, A→C costs 5, C→B costs −4
Dijkstra picks B first (distance 2) and finalises it.
But the real shortest path to B is A→C→B = 5 + (−4) = 1.
B was closed at 2 before that cheaper route was discovered,
and the algorithm never reopens it.
💡 So the answer to "what if edges are negative?" is not that Dijkstra becomes slow — it returns a wrong answer and reports success. Use the Bellman-Ford algorithm instead, which relaxes every edge V−1 times, tolerates negative weights, and detects negative cycles.
What relaxation actually is
The single operation driving the whole algorithm is one comparison:
In words: is going via u cheaper than the best route to v found so far? In the worked example above, B starts at 4 by the direct edge and improves to 3 once C is processed — because 1 + 2 beats 4.
💡 To reconstruct the actual path rather than just its length, record a predecessor whenever relaxation succeeds. Following those predecessors backwards from the destination gives the route — a step questions ask for explicitly and answers often omit.
Complexity, and why the data structure matters
The cost depends entirely on how "the nearest unvisited vertex" is found. Scanning an array gives O(V²); a binary heap gives O((V + E) log V), which is much better on sparse graphs and slightly worse on very dense ones.
This is the same lesson as the graph-representation topic: the algorithm is fixed, and its complexity is decided by the structures underneath it.
Syllabus points
Greedy approach
Dijkstra's algorithm (numerical)
Create a free account to tick topics off, take notes as you read, watch the video lessons and get a day-by-day study plan built around your exam date.