Dijkstra's algorithm
About this app
Shortest paths step by step: build your own weighted graph, choose a start node and follow the D/R table, the visited set and the pseudocode in sync with the node selection in the graph — navigable forward and back.
How Dijkstra finds shortest paths
Dijkstra’s algorithm computes the shortest paths in a weighted graph from one start node to all other nodes. All edge weights must be non-negative. D[i] holds the best known distance to node i, initially ∞ except D[start] = 0. R[i] stores the predecessor on that path, from which the full route can be rebuilt. In each step the candidate h with the smallest D[h] is chosen, its neighbours are checked (relaxation), and h becomes final. With a min-heap the running time is O((|E| + |V|)·log|V|).
What the app shows
You build a directed graph yourself: add nodes, click two nodes in turn to create an edge, change weights, delete edges or nodes and drag nodes around. After choosing the start node the algorithm runs step by step. Alongside you see the table of D and R values, the candidate set MK and the pseudocode for the current step. Each step is explained in words, for example whether an edge improves a distance or not.
Try it yourself
Use “Next” and “Back” to move through the run and watch when a D value drops and which node is chosen next. Build a detour with more edges but a smaller total weight and check that Dijkstra finds it. At the end, read the shortest path backwards via the R values. Once MK is empty, all distances from the start are final.
Frequently asked questions
- How does Dijkstra’s algorithm work?
- It starts with distance 0 at the start node and ∞ everywhere else. It repeatedly picks the open node with the smallest distance and checks its outgoing edges: if the path through it is shorter, the neighbour’s distance is updated. That node is then final.
- Why does Dijkstra fail with negative edge weights?
- Dijkstra marks a node as final as soon as it has the smallest open distance. With negative weights, a later detour could still reduce that distance. For such graphs one uses, for example, the Bellman–Ford algorithm.
- What is the time complexity of Dijkstra’s algorithm?
- With a min-heap priority queue it is O((|E| + |V|)·log|V|). The simple version with a linear search for the minimum takes O(|V|²), which is often fine for dense graphs.
- Can I build my own graph in the app?
- Yes. You add nodes and directed edges, change weights, delete elements and move nodes. Then you choose the start node and step forwards and backwards through the algorithm.
Subject: Linear problems
More from Linear problems
A VisuApp by heyprof: interactive, free in your browser, no sign-up. What is a VisuApp? · All apps