Shortest Path

1. Introduction

What is the Shortest Path?

Shortest Path algorithms find the path between two vertices in a graph such that the sum of the weights of its constituent edges is minimized.

Why is it Important?

In weighted networks, finding the path with the fewest hops is not enough. We must find the path with the lowest overall cost (distance, time, or cost).

Where is it Used?

Routing Protocols: Routing packets through internet gateway nodes (e.g. OSPF) using shortest paths.

Ride Sharing Apps: Calculating the fastest route from pick-up to drop-off.

---

2. Mental Model: Elastic Strings & Relaxation

Imagine a model of nodes connected by elastic strings representing edges:

Place the model on a table. Lift the source node up.

The path strings that pull tight first (taut) represent the shortest paths from the source.

Relaxation: This is the process of updating the shortest distance to a node. If you find a new path to node V through node U that is shorter than its current path, you loosen/update the string (dist[v] = dist[u] + weight(u,v)).

---

3. Shortest Path Algorithms

1. Dijkstra's Algorithm

Dijkstra's is a greedy algorithm that finds the shortest path from a single source to all other vertices.

Mechanism: Maintain a min-priority queue of (distance, vertex). Pop the closest node, relax its neighbors, and push updated distances back.

Constraint: Only works on non-negative edge weights. Negative weights break the greedy assumption (once a node is popped, its distance is finalized).

Time Complexity: O((V + E) log V) using a binary heap.

2. Bellman-Ford Algorithm

Bellman-Ford is a dynamic programming algorithm that solves single-source shortest paths on any graph.

Mechanism: Relax all edges in the graph V - 1 times.

Negative Cycles: Can handle negative edge weights. If a V-th relaxation step still decreases any distance, it means a negative weight cycle exists, making the shortest path undefined (-\infty).

Time Complexity: O(V × E).

---

4. Visualizing Edge Relaxation

Given nodes A, B, and C with values relaxed iteratively:

Initial state: dist[B] = inf, dist[C] = inf.

Relax A -> B and A -> C: dist[B] = 5, dist[C] = 10.

Relax B -> C: dist[C] = min(10, 5 + 2) = 7. Path A -> B -> C is shorter than direct edge A -> C!

---

5. Real-World Examples

Network Routing Protocol (OSPF): Finding shortest paths across internet network hops dynamically.

Flight Connections Pricing: Booking a series of flight connections to minimize overall fare ticket costs.

---

6. Interview Perspective

How Interviewers Ask This Topic

Interviewers test complexity constraints:

"Given a grid containing obstacles and cells with traversal costs, find the cheapest path." -> Model grid as a graph. Use Dijkstra's to search paths since costs are non-negative.

"Why does Dijkstra's fail on graphs with negative weights?" -> Explain that Dijkstra's greedily marks nodes as visited once popped from the priority queue. If a negative weight is processed later, it could yield a shorter path to a previously finalized node, violating the greedy invariant.

Common Mistakes

> 2. Duplicate Queue Overhead: Pushing updated nodes onto the priority queue without checking if a shorter path has already been processed (if (d > dist[u]) continue), causing timeouts on large dense graphs.

---

7. Summary

Dijkstra: Single-source shortest path for non-negative edge weights. Time: O((V+E)log V) using Min-Priority Queue.

Bellman-Ford: Single-source shortest path, handles negative edge weights, detects negative cycles. Time: O(V × E).

Floyd-Warshall: All-pairs shortest path. Time: O(V³).

---

8. Quiz

Question 1: Why does Bellman-Ford relax all edges exactly V - 1 times?

Answer: In a graph with V vertices, the longest simple path (without cycles) can contain at most V - 1 edges. Therefore, V - 1 passes are sufficient to propagate shortest path values to all vertices.

Question 2: What is a negative weight cycle?

Answer: A cycle in which the sum of the weights of the edges is negative. Traversing this cycle repeatedly decreases path distance infinitely, so a shortest path does not exist.

Question 3: If all edges in a weighted graph have identical weights, what algorithm is most optimal?

Answer: Breadth-First Search (BFS), since the graph behaves identically to an unweighted graph, letting us find shortest paths in O(V + E) time instead of O((V + E)log V).

Question 4: True or False: Dijkstra's algorithm always finds the shortest path in a DAG even if it contains negative edges.

Answer: False. Dijkstra's can fail on any graph with negative edges. However, you can find shortest paths on DAGs with negative weights in O(V + E) time by relaxing edges in topological order.

Question 5: What is the space complexity of Dijkstra's algorithm?

Answer: O(V) auxiliary space to store the distance array and the priority queue elements.