Dijkstra's Algorithm

Dijkstra's algorithm employs a greedy approach, meaning it makes the locally optimal choice at each step. It iteratively selects the unvisited node with the smallest tentative distance from the source, permanently settling it. This priority queue-driven selection ensures that once a node is settled, its shortest path is guaranteed, a property that holds only with non-negative edge weights. This greedy paradigm is foundational to more advanced heuristics like A Search*.

A critical limitation is the requirement for all edge weights to be non-negative. The algorithm's correctness proof relies on the fact that adding a non-negative edge to a path cannot decrease its total cost. If negative weights exist, a settled node could later be reached via a shorter path, breaking the greedy invariant. For graphs with negative edges, the Bellman-Ford algorithm must be used instead, which sacrifices speed for generality.

The algorithm solves the single-source shortest path problem. From one origin node, it computes the minimum-cost path to every other reachable node in the graph. This is ideal for logistics scenarios like determining delivery radii from a single warehouse. The output is a shortest-path tree rooted at the source. If only one specific destination is needed, the algorithm can be terminated early once that node is settled, though this does not change its worst-case complexity.

The time complexity depends heavily on the data structures used. With a simple array for the priority queue, it is O(V²) where V is the number of vertices. Using a binary heap, it improves to O((V + E) log V) where E is the number of edges. For dense graphs where E ≈ V², the binary heap offers no benefit. A Fibonacci heap can theoretically achieve O(E + V log V), but high constant factors make it rare in practice for typical logistics graphs.

On continent-scale road networks with hundreds of millions of nodes, raw Dijkstra's is too slow for real-time queries. Techniques like Contraction Hierarchies preprocess the graph by ordering nodes by 'importance' and adding shortcut edges. A bidirectional query then only needs to explore a tiny fraction of the graph. Other methods include Arc Flags and Transit Node Routing, all designed to answer queries in milliseconds by doing heavy computation offline.

Classic Dijkstra's assumes a static graph where edge weights do not change during execution. In dynamic logistics, traffic jams and road closures invalidate the precomputed shortest-path tree. To handle this, variants like D Lite* and Anytime Dynamic A* were developed for robotics and autonomous vehicles. These algorithms reuse previous search results to efficiently repair the solution when edge costs change, avoiding a full recomputation from scratch.