Dijkstra's Shortest Path

Single-source shortest paths on a non-negative weighted graph

From tentative to final distances

Dijkstra's algorithm stores the best distance currently known from one source to every vertex. The source starts at 0 and all other vertices start at infinity. Repeatedly choose the unsettled vertex with the smallest tentative distance, settle it, and relax each outgoing edge.

Watch relaxation change the graph

The amber ring marks the active vertex, green vertices are settled, and the small badge beside each vertex is its current distance. An edge relaxation asks whether reaching a neighbor through the active vertex is shorter than the route stored so far. The final green edges form a shortest-path tree rooted at A.

Set the source distance to 0 and every other distance to infinity.

1function dijkstra(adj: [number, number][][], source: number, n: number): number[] {
const dist = Array(n).fill(Infinity);
dist[source] = 0;
const done = Array(n).fill(false);
for (let k = 0; k < n; k++) {
  let u = -1;
  for (let i = 0; i < n; i++)
    if (!done[i] && dist[i] < Infinity && (u < 0 || dist[i] < dist[u])) u = i;
  if (u < 0) break;
  done[u] = true;
  for (const [v, w] of adj[u]) {
    if (dist[u] + w < dist[v]) {
      dist[v] = dist[u] + w;
    }
  }
}
return dist;
18}

u (current)-

Settled-

dist[A]0

dist[B]∞

dist[C]∞

dist[D]∞

dist[E]∞

dist[F]∞

1 / 32

Why non-negative weights matter

Once the nearest unsettled vertex is chosen, non-negative edges guarantee that no later route can make it cheaper. Negative edges break that argument. With a binary heap, the usual running time is O((V + E) log V).

Typical uses include map routing, network path selection, and any state graph where each move has a non-negative cost. For negative weights, use a different shortest-path algorithm.

Algorithm Visualizer

Dijkstra's Shortest Path

From tentative to final distances

Watch relaxation change the graph

Why non-negative weights matter