Dijkstra (Graph)

Graphs

avgO(V²)worstO(V²)spaceO(V)

Every distance starts at ∞ except the source A, which is 0

1 / 33

Code

function dijkstra(graph: Graph, source: number) {  const dist = new Array(graph.size).fill(Infinity);  const prev = new Array<number | null>(graph.size).fill(null);  const done = new Set<number>();  dist[source] = 0;  while (done.size < graph.size) {    // Settle the unfinished node with the smallest distance.    const u = argMin(dist, (v) => !done.has(v));    if (dist[u] === Infinity) break; // the rest is unreachable    done.add(u);    for (const { to, weight } of graph.edgesFrom(u)) {      if (done.has(to)) continue;      if (dist[u] + weight < dist[to]) {        dist[to] = dist[u] + weight;        prev[to] = u;      }    }  }  return { dist, prev };}function pathTo(prev: (number | null)[], target: number) {  const path = [target];  while (prev[path[0]] !== null) path.unshift(prev[path[0]]!);  return path;}

procedure Dijkstra(G, source)  dist[v] ← ∞ for every node v  prev[v] ← none for every node v  done ← ∅  dist[source] ← 0  while some node is not done do    ▷ the closest unfinished node's distance can no longer improve    u ← the node ∉ done with the smallest dist    if dist[u] = ∞ then stop    ▷ the rest is unreachable    add u to done    for each edge (u, to, weight) do      if to ∈ done then skip it      if dist[u] + weight < dist[to] then    ▷ relax the edge        dist[to] ← dist[u] + weight        prev[to] ← u      end if    end for  end while  return dist, prevend procedureprocedure pathTo(prev, target)  path ← [target]  while prev[first of path] ≠ none do prepend it to path  return pathend procedure

Variables

source=A

Counters

visited: 0
relaxations: 0

Nodes8

Source

Target

Edgesweights 1 to 99

How it works

Dijkstra's algorithm grows a set of settled nodes outward from the source, always settling the unfinished node with the smallest tentative distance and then relaxing its edges. With non-negative weights a settled distance can never improve, so when it finishes every reachable node has its shortest distance. This version scans for the minimum, the classic O(V²) form that suits small dense graphs.

Complexity

Best: O(V²)
Average: O(V²)
Worst: O(V²)
Space: O(V)

Dijkstra (Graph)

How it works

Complexity

Search algorithms