[Djikstra's algorithm]((https://en.wikipedia.org/wiki/Dijkstra%27s_algorithm) is a [[greedy algorithm]] that solves the single source [[shortest path]] problem for a graph with non-negative weights. Djikstra's algorithm updates the [[Bellman-Ford algorithm]] by cleverly ordering the visits along edges. Instead of iterating $n-1$ times, only one iteration is required. At each step, visit the previously visited node with the smallest current estimate of weight. Call `relax` along all outgoing vertices from this node and mark the node as visited. Continue until all nodes have been visited. Use a [[heap]] to manage the calls to `relax`. Djikstra's algorithm runs in $\theta(n + n\log n + m \log n)$ time (near linear time in the number of nodes), much faster than Bellman-Ford's algorithm.