Dijkstra's algorithm

Summary

Dijkstra's algorithm computes the shortest-path distances from one source vertex to all other vertices of a graph whose edge weights are nonnegative. It is a greedy algorithm: it repeatedly settles the unsettled vertex with the smallest tentative distance and updates the tentative distances of its neighbours. With a binary heap it runs in time $O((\abs{V} + \abs{E}) \log \abs{V})$. It needs nonnegative weights; with negative weights one uses the Bellman–Ford algorithm instead.