Glossary · approach
Dijkstra Algorithm
Edsger Dijkstra's (1959) polynomial-time algorithm for single-source shortest paths in graphs with non-negative edge weights; greedy — extract the unvisited node with smallest tentative distance from a priority queue and relax its neighbours; O((V+E) log V) with a binary heap.
Dijkstra's AlgorithmDijkstraDijkstra Shortest PathDijkstra SPF
Dijkstra Algorithm is the polynomial-time algorithm Edsger Dijkstra defined in his two-page 1959 *Numerische Mathematik* paper; it solves the single-source shortest path problem (shortest path from one source node to all other nodes) on a graph with non-negative edge weights. Greedy approach: at each step, extract from a priority queue the unvisited node with the smallest tentative distance and relax (update) its neighbours' distances. Complexity: O((V+E) log V) with a binary heap, O(E + V log V) with a Fibonacci heap. In the single-source single-destination variant, the search stops once the target is reached; for single-source all-destinations, the whole graph is processed. Foundational; a subroutine in countless practical systems (network routing protocols OSPF, navigation, social-network distance, packet switching). A* (Hart-Nilsson-Raphael 1968) is the heuristic-guided variant of Dijkstra; contraction hierarchies (Geisberger 2008) is the modern preprocessing-based extension for country-scale road networks. If a graph contains negative edges, Dijkstra is not optimal — Bellman-Ford is required. Cormen-Leiserson-Rivest-Stein (2009) *Introduction to Algorithms* is the teaching reference.
Örnek
In a field-service operation the shortest-time path from customer 1 to customer 12 is computed in milliseconds on the urban road-network graph by a binary-heap-based Dijkstra; the dispatch centre identifies the closest technician to an incoming emergency call by a single-source all-destinations Dijkstra variant.