How to use the shortest path calculator
- List the connections one per line as from, to, length, for example A, B, 7. Lengths can be distances, costs or times, but they must all use one unit and be 0 or more.
- Choose whether connections go both ways or one way (from the first place to the second).
- Type the start place, and optionally the end place. Leave the end blank to see the shortest distance to every place.
- Read the headline route and distance, then the table of distances and routes to all reachable places.
Formula
distance(start) = 0, every other place begins as unknown
repeat: take the closest place not yet settled, and for each neighbor test whether distance(place) + length is smaller than the neighbor's distance
stop when every reachable place is settled; follow the saved steps back to build a route
This is Dijkstra's method with a priority queue. It gives exact shortest distances whenever no length is negative. Ties between equal routes are broken by the order places are found.
Six places and nine connections
With connections A-B 7, A-C 9, A-F 14, B-C 10, B-D 15, C-D 11, C-F 2, D-E 6 and E-F 9, the shortest way from A to E, going both ways along each connection, is A > C > F > E with a distance of 20 (9 + 2 + 9). The distances from A are B 7, C 9, F 11, D 20 and E 20.
If every connection goes only one way (from the first place to the second), you cannot use F to E, and the shortest route from A to E is A > C > D > E at 26. Starting from E in that one-way graph, only F is reachable at 9. An exhaustive search of every simple path and the Bellman-Ford method both agree with these numbers.
What it is good for
The shortest-path problem appears whenever you have a network and want the cheapest way through it: roads between towns, flights with costs, steps in a workflow with times, or links between computers. Lengths can be anything you want to minimize, as long as the total is the sum of the parts.
The page treats the places as the names you typed, so spelling and capital letters must match from line to line. A place that appears only as an end point still counts as a place.
Related ideas
The shortest route is not the same as visiting every place. For the best order of stops, use the Shortest Visit Order Calculator. For the cheapest way to connect everything with no cycles, the Minimum Spanning Tree Calculator is the right tool, and the Critical Path Method Calculator handles the longest path through a project. Straight-line distances between coordinates are in the Great Circle Distance Calculator.
More math tools
For significant figures, complex numbers, polynomials, repeating decimals and differential equations, try the Significant Figures Calculator, Complex Number Calculator and Polynomial Arithmetic Calculator.
Assumptions and limits
- Every length is a number of 0 or more. Negative lengths need a different method and are refused.
- All lengths use the same unit and add up along a route.
- The graph has at most 300 places and 500 connections.
- Place names are case sensitive and cannot contain commas.
- The example network is an illustration. Replace it with your own.
Frequently asked questions
Why are negative lengths refused?
Dijkstra's method assumes that adding a connection never makes a route shorter. A negative length breaks that, and the answer could be wrong. A different method, Bellman-Ford, handles them but is not part of this page.
What does "No route" mean?
It means there is no chain of connections from the start to the end, or the connections only go the wrong way. The page lists the places that cannot be reached.
What if two routes have the same length?
Both are shortest. The page shows one of them, the one found first. The distance is the same either way.
Can I use road distances?
Yes, enter the length of each road segment. The tool does not know the real map, so it finds the best route through the segments you list.