What the shortest path problem asks
A weighted graph is a set of nodes joined by edges, each edge carrying a number: a distance, a travel time, a cost, a latency, a resistance. The shortest path from one node to another is the route whose edge weights add to the smallest total. Dijkstra's algorithm finds it, and finds the shortest path from your source to every node at the same time, for no extra work.
The word shortest refers to the total weight, not to the number of edges. A four-hop route with weights 2, 3, 4 and 11 beats a two-hop route with weights 4 and 10 whenever 20 is less than 14 - which it is not, so in that case the two-hop route wins. The point is that hop count and total weight are different objectives, and the algorithm optimises the second. Set every weight to 1 and they coincide, which is exactly when a plain breadth-first search would do the same job faster.
The one condition Dijkstra requires is that no weight is negative. That is not a technicality; the algorithm is built on the assumption, and with a negative edge it returns a confidently wrong answer rather than failing. The next section explains why.
Relaxation, and why the greedy choice is safe
The algorithm keeps a tentative distance d(v) for every node - the best route found so far - starting at 0 for the source and infinity for everything else. The single operation it performs is relaxation:
d(v) ← min( d(v), d(u) + w(u, v) )
which asks whether going to v by way of u beats the best route to v already known. If it does, the tentative distance drops and v records u as its predecessor, which is how the path itself is recovered at the end.
The clever part is the order. At each round the algorithm picks the unsettled node with the smallest tentative distance, declares that distance final, and relaxes its outgoing edges. Why is that safe? Because any other route to that node would have to leave the settled region through some other unsettled node, whose tentative distance is already at least as large - and adding non-negative edge weights to it can only make the total larger. The chosen node cannot be improved, so it can be settled.
Follow that argument and you see exactly where a negative weight breaks it. If an edge could reduce the total, a longer detour might come back and undercut a distance already declared final, and the algorithm never revisits a settled node. It does not detect the problem; it just returns the wrong number. The cost of handling negative weights properly is the Bellman-Ford algorithm's O(VE) instead of Dijkstra's near-linear behaviour.
With a binary heap as the priority queue, each of the E edges can trigger one decrease-key operation and each of the V nodes is extracted once, giving O((V + E) log V). A simple scan for the minimum, which is what this calculator does because the graphs are small, gives O(V²) - and that is actually the better choice for dense graphs, where E approaches V² anyway.
Worked example: six nodes, seven edges
Take the graph A-B:4, A-C:2, B-C:5, B-D:10, C-E:3, E-D:4, D-F:11, undirected, and find the route from A to F.
- Start. d(A) = 0, everything else infinite. Settle A and relax its edges: d(B) = 4, d(C) = 2.
- Settle C (smallest tentative distance, 2). Relax: through C, B would cost 2 + 5 = 7, which does not beat the 4 already recorded, so B is unchanged. E becomes 2 + 3 = 5.
- Settle B (distance 4). Relax: D becomes 4 + 10 = 14.
- Settle E (distance 5). Relax: D via E costs 5 + 4 = 9, which beats 14, so d(D) drops to 9 and D's predecessor changes from B to E.
- Settle D (distance 9). Relax: F becomes 9 + 11 = 20.
- Settle F (distance 20). It is the target, and the answer is fixed.
Reading predecessors backwards from F gives F ← D ← E ← C ← A, so the route is A → C → E → D → F with total weight 2 + 3 + 4 + 11 = 20, over four edges.
The obvious-looking alternative A → B → D → F costs 4 + 10 + 11 = 25, and it uses only three edges. Fewer hops, longer route. That is the distinction between hop count and weight, and it is why the extra node in the winning path costs nothing.
Notice step 4. The distance to D was already 14 and had a recorded predecessor when a better route appeared. Relaxation overwrote both. That is normal, and it is why a node's predecessor is provisional until the node is settled - only at the moment of settling does the recorded route become final.
Reading the distance table
The table lists every node with its shortest distance from the source, the node it was reached from, and the full path. Together those predecessor entries form the shortest path tree: a tree rooted at the source in which the unique route to any node is a shortest one. That tree is what a routing table is, and it is why one run of the algorithm answers every destination at once.
Nodes marked unreachable lie in a different connected component of the graph, or - in a directed graph - are only reachable against the arrows. Reachability is direction-sensitive, so a directed graph can easily have a route from A to B and none from B to A. Toggle the directed switch to see the difference on your own edge list.
Shortest paths are not always unique. When two routes tie, the algorithm returns one of them and the tie is invisible in the output. If the choice matters - because ties correspond to genuinely different physical routes - perturb one weight slightly and see whether the reported path changes.
Every prefix of a shortest path is itself a shortest path. That property, called optimal substructure, is what makes the whole approach work, and it gives you a free check on any answer: if the route to F runs through D, the distance shown for D must equal the distance to F minus the weight of the final edge. In the worked example, 20 − 11 = 9, which is exactly d(D).
Choosing a shortest-path algorithm
| Algorithm | Solves | Negative weights? | Complexity | Use when |
|---|---|---|---|---|
| Breadth-first search | One source, all targets | N/A - unweighted | O(V + E) | Every edge has the same weight |
| Dijkstra (binary heap) | One source, all targets | No | O((V + E) log V) | Sparse graph, non-negative weights |
| Dijkstra (array scan) | One source, all targets | No | O(V²) | Dense graph, or a small one like this page |
| A* search | One source, one target | No | O((V + E) log V) worst case, far less in practice | You have an admissible distance estimate, as in map routing |
| Bellman-Ford | One source, all targets | Yes, and detects negative cycles | O(VE) | Currency arbitrage, any graph with negative edges |
| Floyd-Warshall | All pairs | Yes, no negative cycles | O(V³) | You need every pairwise distance and V is small |
| Johnson | All pairs | Yes, no negative cycles | O(V² log V + VE) | All pairs on a large sparse graph |
A* reduces to Dijkstra when the heuristic is identically zero, which is why it is best understood as Dijkstra with a hint rather than as a separate algorithm.
Pitfalls
- Negative edge weights. The greedy settling step is invalid and the answer is silently wrong. This calculator refuses to run rather than mislead you. Bellman-Ford is the correct tool.
- Forgetting the graph is directed. An undirected edge is two directed edges. If you enter one-way streets, tick the directed box, or every route will be allowed to run backwards.
- Assuming the fewest hops is the shortest route. Only when all weights are equal. Otherwise a longer chain of cheap edges routinely beats a short chain of expensive ones.
- Case-sensitive node names.
aandAare different nodes, so a stray capital creates an isolated node that is unreachable from everything. - Expecting a unique answer when weights tie. Several routes can share the minimum total. The algorithm reports one; there is no error.
- Treating a large distance as unreachable. They are different: unreachable means no route exists at all, and it appears explicitly in the table rather than as a big number.
Where the algorithm is used
Edsger Dijkstra devised the algorithm in 1956 and published it in 1959, in a three-page paper that also gave a minimum spanning tree method. He described designing it in about twenty minutes in a cafe in Amsterdam, without pencil and paper, as a demonstration problem for a new computer. It remains one of the most-used algorithms in existence.
Network routing is the largest application. The OSPF protocol that moves packets inside most large IP networks runs Dijkstra over a link-state database, with weights derived from link bandwidth; IS-IS does the same. Every router recomputes the shortest path tree from itself when the topology changes, which is exactly the tree this calculator reports.
Map routing uses the A* variant, which adds a straight-line distance estimate to steer the search towards the destination rather than expanding uniformly in all directions. When that estimate never overstates the true remaining distance - the condition called admissibility - A* is guaranteed to find the same optimal path as Dijkstra while examining far fewer nodes.
Beyond geography, the same formulation covers project scheduling on a task network, minimum-cost flow in logistics, word-similarity chains, and any problem you can phrase as nodes plus additive non-negative costs. Since a graph is naturally stored as an adjacency matrix, several of these problems also have a linear-algebra reading; the connections between graph structure and matrix properties are the subject of spectral graph theory, where the eigenvalues of the adjacency or Laplacian matrix encode connectivity. For the discrete-structures background, the set operations and logic pages cover the rest of the standard toolkit.