Dijkstras

Dijkstra's algorithm is a method for finding the shortest paths from a single source vertex to all other vertices in a weighted graph, provided all edge weights are non-negative. It operates by maintaining a set of vertices with confirmed shortest distances and a priority queue of candidate vertices ordered by their current distance estimates. Starting with the source at distance zero, the algorithm repeatedly selects the unvisited vertex with the smallest distance, marks it as visited, and relaxes its outgoing edges, updating neighbor distances and predecessors when a shorter path is found.

Key implementation details include the use of a graph representation such as an adjacency list and a min-priority queue (often a binary heap). The typical time complexity with a binary heap is O((V + E) log V), commonly stated as O(E log V), and the space complexity is O(V + E) to store the graph, distance estimates, and predecessor information. Variants that use more sophisticated priority queues, such as Fibonacci heaps, can improve theoretical bounds to O(V log V + E).

Dijkstra's algorithm can be applied to directed or undirected graphs with non-negative weights. If a graph contains negative edge weights, the algorithm may produce incorrect results; in such cases alternatives or preprocessing steps, such as Johnson's algorithm (which reweights edges) or Bellman-Ford, are used. Dijkstra's algorithm also underpins several extensions and related methods, including A* for heuristic-guided search and bidirectional variants that run searches from both ends to reduce exploration.

Origins and impact: the algorithm was introduced by Edsger W. Dijkstra in 1959 and has become a foundational technique in computer science, with broad use in routing, navigation, robotics, and network analysis.