Djisktra's Algorithm

Hard

Greedy shortest paths with non-negative weights

Problem

Find shortest paths from a source in a graph with non-negative weights using a priority queue.

In simple words

Always expand the closest unfinalised node (min-heap), relaxing its neighbours' distances.

The idea

Dijkstra keeps a set of 'settled' nodes whose shortest distance is locked in. Each step it settles the closest unsettled node — a greedy choice that is safe precisely because no edge is negative, so a cheaper route can never appear later. After settling a node it relaxes its edges, offering neighbours a shorter distance. A min-priority-queue hands you that closest node in O(log V).

The trick

Once a node is popped from the heap its distance is final — non-negative weights guarantee no cheaper route can appear later.
'Relaxing' an edge is one question: is reaching my neighbour through me cheaper than its current best? If so, lower it.
Negative edges break the greedy guarantee — use Bellman-Ford instead.

←→stepspaceplay

dist[0, ∞, ∞, ∞, ∞]

settled—

1/13

Optimal

timeO(E log V)spaceO(V)

1dist[src] = 0, all others = ∞2min-heap H = {(0, src)}3while H not empty:4  (d, u) = pop-smallest from H      // closest unfinished node5  for each edge (u → v, weight w):6    if d + w < dist[v]:             // relaxation7      dist[v] = d + w; push (dist[v], v)8return dist

Input

nodes: 5, 6 edges

Memory

dist: [0, ∞, ∞, ∞, ∞]
frontier: —

Output

settled: —
shortest dist: —

Check yourself

3 quick questions about this walkthrough. A wrong answer costs nothing.

Examples

Example 1

Input:: n = 5, edges = [[0,1,4],[0,2,1],[2,1,2],[1,3,1],[2,3,5]], src = 0
Output:: [0, 3, 1, 4, inf]
Explanation:: Shortest distance from 0 to every node.

Example 2

Input:: n = 2, edges = [[0,1,7]], src = 0
Output:: [0, 7]
Explanation:: 0→1 costs 7.

Example 3

Input:: n = 3, edges = [[0,1,1],[1,2,1]], src = 0
Output:: [0, 1, 2]
Explanation:: Distances 0,1,2.

Practice this problem:LeetCode(opens in a new tab)Search GeeksforGeeks(opens in a new tab)

Finished the walkthrough? Add it to your streak.