Dijkstra's Algorithm

BFS finds the shortest path in unweighted graphs. But what if connections have different costs (e.g., distance or traffic)? Dijkstra's Algorithm is the world's most famous solution for finding the shortest path in Weighted Graphs.

1. How it Works (Greedy + DP)

Dijkstra uses a Priority Queue (Min-Heap).

1. Set distance to all nodes to Infinity (except Start = 0).
2. Pick the unvisited node with the smallest distance.
3. For each neighbor, calculate NewDistance = CurrentDistance + EdgeWeight.
4. If NewDistance < ExistingDistance, update the neighbor and add it to the Priority Queue.

2. The "No Negative Weights" Rule

Dijkstra is a greedy algorithm. It assumes that once it "relaxes" a node, it has found the absolute shortest path. This only works if all edge weights are positive. If you have negative weights (e.g., a "Cashback" on a path), you must use the Bellman-Ford algorithm instead.

4. Interview Mastery

Q: "Where is Dijkstra used in modern software architecture?"

Architect Answer: "It is the heart of **OSPF (Open Shortest Path First)** routing protocols that power the internet. It is also used by **Google Maps** (though with more advanced heuristics like A*) to find the fastest route between two cities. In microservices, it can be used for 'Service Discovery' to find the instance with the lowest latency."