Dijkstra Shortest Path Calculator

Dijkstra's algorithm finds the shortest paths from one node to every other node in a graph whose edge weights are not negative — the basis of route planners, network routing and many textbook exercises. Enter the edges as a list, pick the start (and optionally the end) node, and this calculator gives every shortest distance and path plus a step-by-step table of which node is visited and which distances are updated, the way the algorithm is traced by hand.

How to use this tool

1. Enter one edge per line: from, to and weight (A B 4).
2. Tick "Directed" for one-way edges, or leave it off for two-way edges.
3. Type the start node and, optionally, the end node.
4. Read the distance and path, the table for all nodes, and the steps.

Formula

repeat: visit the unvisited node u with the smallest d(u); for each edge u → v of weight w: if d(u) + w < d(v), set d(v) = d(u) + w and prev(v) = u

All distances start at ∞ except the start node (0). Once a node is visited its distance is final, which is only guaranteed when no weight is negative — so negative weights are refused (Bellman–Ford handles them). Paths are rebuilt by following prev back to the start. Ties go to the node listed first. Parallel edges are allowed; the cheaper one wins.

Example

The sample is the directed graph from Figure 24.6 of Introduction to Algorithms (CLRS). From s, the visits are s (0), y (5), z (7), t (8) and x (9). The shortest route to x is s → y → t → x with length 9: 5 + 3 + 1. The direct-looking s → t edge (10) loses to s → y → t (8).