Dijkstra's Shortest Path Screensaver
The Dijkstra's Shortest Path screensaver runs a real live Dijkstra's algorithm on a random weighted graph, showing the expanding wavefront of confirmed shortest distances. It is free, runs in your browser, and ESC exits.
Live preview
Press ESC to leave fullscreen. Settings are saved in your browser only.
How the Dijkstra's Shortest Path screensaver works
The saver generates a real random graph of nodes and weighted edges, then runs Dijkstra's algorithm from a single source node.
Each step pulls the real closest unvisited node from the frontier, locks in its shortest distance, and relaxes its neighbors' distances.
The locked-in shortest-path tree grows outward frame by frame, exactly as the real algorithm computes it, node by node.
Once every reachable node is finalized, the graph fades and a fresh random graph and source node begin.
Edsger Dijkstra and the shortest-path idea
The Dutch computer scientist Edsger Dijkstra conceived this algorithm in 1956 at the Mathematical Centre in Amsterdam and published it in 1959. He later recalled designing it in about twenty minutes, without pencil and paper. It answers a simple question on a graph whose edges carry non-negative costs: what is the cheapest route from one starting node to every other node? Road maps, network routing and game pathfinding all rest on the same idea.
The method works by always finalising the closest node not yet settled. Once that node is settled, no later route can beat it, because every other candidate is at least as far away and edge costs cannot be negative. The algorithm then checks whether going through the new node gives its neighbours a shorter path, which is the step called relaxation. Repeating this makes the settled region grow outward like a ripple.
The non-negativity requirement is essential. With negative edge weights the argument that a settled node is final breaks down, and algorithms such as Bellman-Ford are used instead. Run time depends on how the frontier is stored; with a binary heap the worst case is proportional to (edges + nodes) times the logarithm of the nodes.
A worked example
A node just three hops away but behind a costly edge gets its shortest distance locked in later than a farther node reached by cheaper edges, exactly matching real weighted-shortest-path behavior.
Settings & tips
- Accent recolours the confirmed shortest-path tree.
- The graph and edge weights are real and randomized every run.
- A fresh graph generates automatically once every node is finalized.
Frequently asked questions
- Is this the real Dijkstra's algorithm?
- Yes — a real, correct implementation, run live on a randomized weighted graph.
- What does the wavefront represent?
- The real, growing set of nodes whose shortest distance from the source has been finalized.
- Is a key needed?
- No — it is a pure local computation.
- Is it free?
- Yes — free, no download, in your browser.
- Why can't Dijkstra's algorithm handle negative edges?
- Its correctness depends on a settled node being final. A negative edge could later make a path through a farther node cheaper, which would invalidate that guarantee.
- How is this different from A*?
- A* adds a heuristic estimate of the remaining distance to a target, so it can explore fewer nodes when there is one destination. Dijkstra explores uniformly in all directions.
- What is relaxation?
- It is the step of testing whether a route through a newly settled node gives a neighbour a lower total cost than the best one known so far, and updating that cost if so.