Dijkstra's Shortest Path

When to Use Dijkstra

• Shortest path with non-negative edge weights
• Routing (road networks, latency graphs)
• Weighted grid pathfinding (terrain cost)
• As a subroutine in Johnson's algorithm

Core Idea

Maintain a set of settled vertices whose distances are finalized. Keep a priority queue of frontier vertices keyed by tentative dist. Extract the minimum, settle it, and relax all outgoing edges—updating neighbors' tentative distances if a shorter path is found.