GraphLab

Graph theory & algorithm visualizer
About Dijkstra's algorithm

GraphLab › Dijkstra's algorithm

Dijkstra's Algorithm Visualizer: Shortest Path Step by Step

Dijkstra's algorithm finds the shortest path from a start vertex to every other vertex in a weighted graph, as long as no edge has a negative weight. It is the idea behind route planning in maps and in computer networks.

How it works

  1. Give the start vertex distance 0 and every other vertex distance ∞.
  2. Pick the unvisited vertex with the smallest distance and mark it visited.
  3. For each edge leaving it, check whether going through this vertex gives a shorter distance to the neighbour. If it does, update the neighbour's distance.
  4. Repeat until every reachable vertex is visited. Follow the saved "previous vertex" links back from the end vertex to read off the shortest path.

Try it in GraphLab

Tap the start vertex, then the end vertex. Use Next to watch the distance table change one step at a time. Edit the graph or the edge weights and the result updates.

More topics