Dijkstra’s Complexity

Dijkstra’s algorithm inspects each of the nodes that have not yet been permanently labelled, so the work per step is approximately proportional to the number of remaining nodes. For the entire process this number is:

(n - 1) + (n - 2) + (n - 3) + \dotsc + 1 = \frac{1}{2}n(n - 1).

Dijkstra’s algorithm has quadratic complexity.