Dijkstra (shortest path)

O((V + E) log V)

Dijkstra's algorithm finds the shortest path from a source to every other node in a graph with non-negative edge weights. It keeps a tentative distance for each node and repeatedly finalizes the closest unvisited one, relaxing its neighbours (lowering their distance when a shorter route is found). Here each edge's weight is the straight-line distance between its endpoints, so drag the nodes to change the costs. It powers routing and network shortest-path problems.

Click empty space = vertex · click two vertices = edge · drag = moveStart: A
Input graph
Edit the input and press Play

How it works

  1. Set the start's distance to 0 and every other node to ∞.
  2. Pick the unvisited node with the smallest tentative distance and finalize it.
  3. Relax its neighbours: if going through it is shorter, lower their distance and set their parent.
  4. Repeat until every reachable node is finalized.

Pseudocode

1dijkstra(graph, start):             # O((V+E) log V)2  dist[start] ← 0; all others ← ∞3  while unvisited nodes remain:4    u ← unvisited node with the smallest dist5    for each neighbour v of u:6      if dist[u] + w(u,v) < dist[v]:    # a shorter path7        dist[v] ← dist[u] + w(u,v); parent[v] ← u8    mark u visited                      # dist[u] is now final