Shortest Path Generator
A weighted graph, two ends, and the cheapest route between them. Dijkstra settles nodes in order of distance, which is why it never needs to revisit one — and why it fails on negative weights, which never appear here. The answer is checked by the condition that defines shortest distances: no single edge may offer a cheaper way to reach anywhere.
What this generator does
Builds a connected weighted graph and finds the cheapest route from the first node to the last, along with the shortest distance to every other node. The route is shown edge by edge with the total, and the direct edge is called out where one exists.
How to use this tool
- Choose the graph size and how many extra edges to include.
- Find the cheapest route from the first node to the last.
- Compare against the route and distance shown.
- Seed the graph to attempt the identical problem again.
Understanding the controls
- How many nodes
- Between 4 and 12. Larger graphs make the route harder to find by hand without changing the method.
- Extra edge density (%)
- More edges give more alternative routes, which is what makes the shortest one worth computing.
- Seed
- Reproduces the same graph and weights exactly.
Common use cases
- Practice instances for Dijkstra with a verified answer
- Showing that the direct edge is often not the cheapest route
- Test cases for a routing implementation
- Teaching why shortest-path distances satisfy the relaxation condition
- Reproducing a specific graph from a seed
How this generator works
Dijkstra repeatedly settles the nearest unsettled node and relaxes its edges. The check does not re-run it: it confirms the stated route uses real edges summing to the stated distance, then tests every edge in the graph for a shortcut. If any edge could reach a node more cheaply than the recorded distance, these were not shortest distances.
Randomness and fairness
The graph and its weights are random; the route is computed and verified. Seeded graphs reproduce exactly and are therefore explicitly not cryptographically secure, and unseeded ones use the browser's cryptographically secure generator.
For how randomness is produced across the whole site, see how Generate Random works.
Limitations and good to know
- Weights are positive whole numbers. Dijkstra is wrong on negative weights, so they are never generated.
- The route always runs between the first and last node rather than a pair you choose.
- Undirected graphs only — one-way networks are the flow generator's territory.
- No map or drawing; the graph is given as an edge table.
- Graphs are not saved between visits.
Privacy and your data
The graph, the route and the distances are computed in your browser. Nothing is transmitted or retained.
Related generators
- Minimum Spanning Tree GeneratorWeighted graphs with the cheapest spanning tree found by Kruskal and, at small sizes, confirmed against every other spanning tree.
- Graph Traversal GeneratorThe same graph visited breadth-first and depth-first side by side, with the hop count each node sits at.
- Random Graph GeneratorRandom graphs at a density you choose, drawn and exported as an edge list or DOT, with connectivity measured rather than assumed.
- Flow Network GeneratorCapacitated networks with the maximum flow found by Edmonds-Karp and the minimum cut that proves it cannot be beaten.