Dijkstra's Shortest Path Algorithm is a deterministic method for finding the least-cost path from one source node to every other node in a weighted graph whose edge costs are all non-negative. It keeps a tentative distance for every vertex, repeatedly settles the unsettled vertex with the smallest tentative distance (a greedy choice), and relaxes that vertex's outgoing edges, lowering neighbours' tentative distances whenever a shorter route is found; distances only ever decrease, and once a vertex is settled its distance is final. An implementation needs a graph representation (adjacency list or matrix), a weight function, and a priority queue keyed on tentative distance, giving \( O((V + E) \log V) \) time with a binary heap. The non-negative-weight requirement is essential: a negative edge can make an already-settled vertex reachable more cheaply, so graphs with negative costs need Bellman-Ford instead. It is the standard single-source shortest-path routine in graph theory and underlies route planning, network routing and least-cost-path analysis on grids.
Dijkstra's algorithm is a greedy graph algorithm that computes the shortest path from a fixed source node to every other node in a weighted, connected graph. It maintains a tentative shortest-distanc…