Graph Algorithms

Three classical shortest-path algorithms with different tradeoffs:

Dijkstra's key insight: greedy. At each step, pick the unvisited node with smallest distance, then relax all its neighbours. Once a node is finalized, its distance is correct.

dist[source] = 0; dist[others] = ∞
PQ = {source}
while PQ not empty:
  u = extract min from PQ
  for each neighbour v of u:
    alt = dist[u] + weight(u, v)
    if alt < dist[v]:
      dist[v] = alt
      add (alt, v) to PQ

Why Dijkstra fails with negative weights: the greedy choice ("smallest distance is final") can be wrong if a longer path with a negative edge improves things later.

Bellman-Ford is iterative — relax ALL edges V−1 times. After V−1 iterations, all SSSP distances are correct (any path has ≤ V−1 edges in shortest form). A V-th iteration that still relaxes an edge proves a negative cycle exists.

Floyd-Warshall uses dynamic programming:

for k from 1 to V:
  for i from 1 to V:
    for j from 1 to V:
      dist[i][j] = min(dist[i][j], dist[i][k] + dist[k][j])

Where dist[i][j] uses only intermediate vertices in {1, ..., k}. Simple and fast for dense graphs.

Common GATE traps:

• Dijkstra with priority queue and min-heap: O((V+E) log V). With Fibonacci heap: O(E + V log V).
• Bellman-Ford works on directed graphs; for undirected with negative edge, you'd have a negative cycle (down then back).
• The "subpaths of shortest paths are shortest paths" principle (optimal substructure) underpins all three.