Shortest Path Calculator
Find the shortest path between two vertices using Dijkstra's algorithm on a weighted edge list.
About Shortest Path Calculator
Dijkstra's algorithm finds the shortest path from a source vertex to all other vertices in a weighted graph with non-negative edge weights. It works by greedily selecting the unvisited vertex with the smallest tentative distance.
Formula
For each unvisited vertex u with min distance d[u]: for each neighbor v, if d[u]+w(u,v) < d[v], update d[v]
- d[v]
- Tentative shortest distance to v
- w(u,v)
- Edge weight from u to v
Worked example
With the default values below, Shortest Path Calculator returns Shortest Distance of 10.0000. Change any input above and every figure here is recalculated in your browser.
Inputs used
- Edges (format: A-B:weight; ...)
- A-B:4; A-C:2; B-C:1; B-D:5; C-D:8; C-E:10; D-E:2
- Source Vertex
- A
- Target Vertex
- E
Results
- Shortest Distance
- 10.0000
- Shortest Path
- A → C → B → D → E
- Vertices Visited
- 4
Step by step
- 1Values used
- 2Formula applied
- 3Shortest Distance= 10.0000
- 4Shortest Path= A → C → B → D → E
- 5Vertices Visited= 4
Assumptions and limits
- The result is derived only from the 3 inputs listed above. Anything not among them is not part of the calculation.
- In particular, this calculator does not take inflation, tax, fees or charges or compounding frequency into account.
- Figures are rounded for display to 4 decimal places, so totals built from several rounded parts can differ slightly from the unrounded arithmetic.
How these calculators are built and tested is described on the Methodology page. If a figure looks wrong, please report it.
Frequently Asked Questions
Can Dijkstra handle negative edge weights?
No. For graphs with negative edges, use the Bellman-Ford algorithm. Dijkstra assumes all edge weights are non-negative.
What is the time complexity?
O(V²) with a simple array, or O((V+E) log V) with a priority queue, where V is vertices and E is edges.