CSE221 · Algorithms

Dijkstra's Simulator

Relax edges one at a time and watch the distance table settle into shortest paths.

CSE221 lectures
42632581734A0B∞C∞D∞E∞F∞G∞H∞

Start at A with distance 0. Every other node starts at infinity.

step 1 of 21
expanding nowinspectingin frontierdone / in treeuntouched

Dijkstra's Algorithm

Repeatedly settles the unvisited node with the smallest tentative distance, then relaxes its edges. Needs non-negative weights.

Time
O((V + E) log V)

Priority queue (by distance)

A

Highlighted entry comes out next.

Build your graph

—

Edges (11)

  • A — B(4)
  • A — D(2)
  • B — C(6)
  • B — E(3)
  • C — F(2)
  • D — E(5)
  • D — G(8)
  • E — F(1)
  • E — G(7)
  • F — H(3)
  • G — H(4)
Start node

← → to step, or use the buttons above.