Shortest Path Calculator
Find the shortest path between two vertices using Dijkstra's algorithm on a weighted edge list.
Inputs
Weighted edge list. Format: X-Y:weight separated by semicolons.
Shortest Distance
10.0000
Shortest Path
A → C → B → D → E
Vertices Visited
4
Step by step
Values 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
Formula applied
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]
Shortest Distance
= 10.0000
Shortest Path
= A → C → B → D → E
Vertices Visited
= 4
How it works
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
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.