Dijkstra's algorithm finds shortest paths from one source when every edge weight is nonnegative.

The algorithm maintains a tentative distance $d(v)$ for each vertex. Repeatedly, it selects the unsettled vertex with smallest tentative distance and relaxes its outgoing edges:

$$d(v)\leftarrow\min\bigl(d(v),d(u)+w(u,v)\bigr).$$

With nonnegative weights, once the smallest tentative vertex is selected, no later route can improve its distance. This is the greedy step that makes the algorithm correct.

A priority queue efficiently selects the next vertex. With an adjacency-list graph and a binary heap, a common bound is

$$O((|V|+|E|)\log |V|).$$

Dijkstra's algorithm must not be applied blindly to graphs with negative edge weights; its finalization argument then fails.