Shortest Path Algorithms: Dijkstra, Bellman-Ford and Floyd-Warshall with Worked Examples for GATE CS

You know what a shortest path is, but “after two Bellman-Ford passes, what is d[C]?” can still make you freeze. The real problem is selection and tracing: shortest paths use one idea, relaxation, scheduled in different ways. Relaxation is scheduled differently in each algorithm, leading to different traces, complexities, traps, and applications in GATE and interviews.

The shortest-path family and the idea underneath

A single-source problem asks for distances from one vertex to all others. Single-pair is a special case with no known asymptotically better general solution. All-pairs asks for every ordered vertex pair.

The common operation is relaxation. For an edge (u, v) of weight w, if d[u] + w < d[v], set d[v] = d[u] + w and parent[v] = u. The algorithms differ mainly in which edge they relax next.

Memorise this decision map:

• Unweighted graph: BFS in O(V + E).

• DAG with any edge weights: topological-order relaxation in O(V + E).

• Non-negative weights: Dijkstra.

• Negative edges possible: Bellman-Ford.

• All pairs on a dense graph: Floyd-Warshall is often a good fit.

The Advanced Algorithms for GATE CS guide positions graph methods among divide and conquer, greedy, and dynamic programming. Once shortest paths are the right family, edge weights and source count determine the method.

Dijkstra traced end to end

Dijkstra repeatedly extracts the unfinalised vertex with the smallest tentative distance, finalises it, and relaxes its outgoing edges. This greedy choice is safe only with non-negative weights, when no later route can beat a finalised distance.

Take a directed graph with edges S->A=4, S->B=1, B->A=2, A->C=5, B->C=8, A->D=6, and C->D=3. Start with d=(S:0, A:inf, B:inf, C:inf, D:inf).

The final distances are S=0, B=1, A=3, C=8, D=9. Parent pointers give S -> B -> A -> D, costing 1+2+6=9. A improved from 4 to 3 through B, while the late route through C could not improve D. Extraction order controls Dijkstra.

Negative edges and Bellman-Ford

A four-vertex counterexample uses S->A=3, S->B=8, B->C=-6, and C->A=-4. Dijkstra finalises A at 3 before B because 3 is smaller than 8. After B creates C=2, the edge C->A would lower A to -2, but A is already finalised. The true path S->B->C->A costs 8-6-4=-2, so the reported 3 is wrong.

Bellman-Ford does not finalise vertices. It relaxes every edge V-1 times. With edge order C->A, B->C, S->B, S->A and V=4, pass 1 sets B=8 and A=3. Pass 2 sets C=2; pass 3 then lowers A to -2. A fourth scan changes nothing, so there is no reachable negative cycle. Intermediate values depend on edge order, but final distances do not.

Run one extra pass for cycle detection. If a reachable distance improves, a reachable negative cycle makes its shortest path undefined. In an undirected graph, one negative edge creates such a cycle by crossing it and returning. “Bellman-Ford handles negatives” quietly assumes a directed graph.

Floyd-Warshall as dynamic programming

Let D_k[i][j] be the shortest i-to-j distance using only vertices 1..k as intermediates. Then D_k[i][j] = min(D_(k-1)[i][j], D_(k-1)[i][k] + D_(k-1)[k][j]). Therefore k must be the outermost loop. The dynamic programming guide explains this subproblem viewpoint.

For edges 1->2=3, 1->4=7, 2->1=8, 2->3=2, 3->1=5, 3->4=1, and 4->1=2, start with:

D0 = 0  3  inf  7
     8  0   2    inf
     5  inf 0    1
     2  inf inf  0

When k=2, route 1->2->3 creates 1->3=3+2=5. The k=3 round changes 1->4 to 5+1=6, 2->1 to 2+5=7, and 2->4 to 2+1=3. Finally, k=4 makes 2->1=3+2=5, 3->1=1+2=3, and 3->2=1+5=6.

D4 = 0  3  5  6
     5  0  2  3
     3  6  0  1
     2  5  7  0

The exam-favourite cell is 2->4=3, through 2->3->4, instead of the infinity with which it started.

Complexities and algorithm selection

When E is near V^2, array Dijkstra can beat the heap version. On sparse graphs, heap Dijkstra from every vertex in O(V(V+E) log V) can beat Floyd-Warshall. “All pairs means Floyd-Warshall” is a trap. Floyd-Warshall detects a negative cycle when a diagonal entry becomes negative.

Traps that cost marks

• Finalisation: Never choose Dijkstra if any edge is negative. Scan edge signs before naming the algorithm.

• Iteration count: Bellman-Ford needs V-1 passes in the worst case but may converge earlier. The minimum depends on the edge count of a longest shortest path. Values after a named pass depend on the given edge order.

• Loop order: Putting k inside the i and j loops breaks Floyd-Warshall's subproblem invariant and can produce a plausible but wrong matrix.

• Path reconstruction: Distances alone do not recover paths. Keep parent pointers for Dijkstra and Bellman-Ford, or a successor matrix for Floyd-Warshall.

How GATE and interviews test shortest paths

GATE commonly asks for traces after stated extractions or passes, one final NAT distance, MSQs about negative edges, and complexity comparisons. The official GATE question-paper pattern page lists the MCQ, MSQ and NAT formats; confirm current details there.

The idea crosses subjects. Distance-vector routing applies Bellman-Ford-style relaxation, while link-state routing runs Dijkstra. Interviews ask you to implement heap Dijkstra, justify its complexity, adapt BFS to grids, or explain why negatives rule Dijkstra out.

After one hand trace of each algorithm, practise a mixed timed set. The GATE Test Series provides topic-wise tests and full mocks across traces, conditions and complexity.

The short version and where to go next

• Every shortest-path algorithm repeatedly relaxes edges in a chosen order.

• Dijkstra is greedy and requires non-negative weights.

• Bellman-Ford allows negatives; an improving extra pass reveals a reachable negative cycle.

• Floyd-Warshall grows the allowed intermediate set with k outermost in O(V^3).

• Choose from edge signs and source count, not habit.

Hand-trace each algorithm once more on a graph you draw yourself. For Algorithms taught in sequence with lectures and practice, continue with Zero to Hero, Complete CS Course. The GATE CS Exam Preparation hub connects this topic to the rest of the subject sequence.