Dijkstra Shortest Path

Hard

Always finalise the closest unfinished node, then relax its outgoing edges. Requires non-negative weights.

priority queuegreedyweighted

TimeO(E log V)

SpaceO(V)

Inputweighted edges u-v:w | source

0@0

Source is 0. Everything else starts at infinity.

1 / 21

dist[src] = 0; pq = {(0, src)}

while pq:

(d, u) = pq.pop_min()

if d > dist[u]: continue

for (v, w) in adj[u]:

if d + w < dist[v]: dist[v] = d + w; pq.push((dist[v], v))

Why it matters

The greedy argument breaks with negative edges, where you need Bellman-Ford.

Practise this

Keyboard

space play← → stepr restartctrl K search

More in Graphs