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.
Dijkstra uses a Priority Queue (Min-Heap).
NewDistance = CurrentDistance + EdgeWeight.NewDistance < ExistingDistance, update the neighbor and add it to the Priority Queue.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.
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."