- Current
- In the queue
- Final
- Path
Dijkstra's algorithm
Dijkstra's algorithm finds the shortest route from a start to every other node when the edges have lengths, like roads between towns. It grows outward from the start, always taking the nearest node it has not finished yet. Click a node to start from it, pick a goal if you like, and step through to see the queue, every distance drop as shorter ways turn up, and the shortest path appear. Press Play to watch the search, or Step and Back to go one step at a time. Drag the step slider to jump anywhere. Click a node to make it the start; switch the click to Goal and click another node to look for a shortest path to it. The number on each edge is its length, the number on each node its shortest distance so far, and the row under the graph is the queue, nearest first. New graph makes another graph; choose how many nodes and edges it has. With the board selected, the arrow keys step, the space bar plays and pauses, and Home and End jump to the start and the end.
How it works
- Click a node to make it the start. To look for a path, switch the click to Goal and click another node.
- Press Play, or use Step and Back to move one step at a time. Drag the step slider to jump anywhere in the search.
- Watch the queue under the graph and the distance on each node. New graph makes another graph to try.
How Dijkstra's algorithm works
Give the start distance 0 and every other node infinity, and put the start in a queue. Then repeat: take the node in the queue with the smallest distance, and mark that distance final. For each of its neighbours that is not final, add the length of the edge to the node's distance. If the sum is shorter than the neighbour's distance so far, it becomes the new distance, the node is remembered as the way there, and the neighbour joins the queue if it was not in it. When the queue is empty, every node that can be reached has its shortest distance.
Why the nearest node is final
When a node is the nearest in the queue, every other way to it must leave the finished part of the graph through some node in the queue, which is at least as far away, and then add edges that cannot be negative. So no other way can be shorter. That is also why a goal is only certain when it is taken from the queue, not when it is first reached, and why Dijkstra's algorithm fails with negative edges: there, the Bellman–Ford algorithm is needed. When every edge has length 1, Dijkstra's algorithm does the same as breadth-first search.
Frequently asked questions
What is Dijkstra's algorithm?
A way to find the shortest paths from one start node to all other nodes in a graph whose edges have lengths that are zero or more. It repeatedly takes the nearest unfinished node, makes its distance final, and uses its edges to shorten the distances of its neighbours.
Why does Dijkstra's algorithm not work with negative edges?
It makes a node's distance final as soon as the node is the nearest in the queue. A negative edge found later could still lead back to that node by a shorter way, so the final distance could be wrong. The Bellman–Ford algorithm handles negative edges, as long as there is no cycle with a negative total.
What is the difference between Dijkstra and BFS?
Breadth-first search counts edges and uses a plain queue. Dijkstra's algorithm adds up edge lengths and uses a priority queue that always gives the nearest node. With every edge of length 1, both find the same distances.
How fast is Dijkstra's algorithm?
With a binary heap as the priority queue, the work grows with (V + E) log V for V nodes and E edges. With a Fibonacci heap it is E + V log V. The app keeps the queue as a sorted list, which is simple to show and fine for small graphs.
Is my graph sent anywhere?
No. The graph is made and searched in your browser, and your last settings stay in this browser's local storage.
Ready to try it?
Open PictorX in your browser — no install, no credit card required to start.
Go to Editor