Shortest Path Calculator (Dijkstra's Algorithm)

Dijkstra’s Algorithm

Published in 1959 by Dutch computer scientist Edsger W. Dijkstra, this algorithm finds the shortest path between vertices in a weighted graph with non-negative edge weights.

How It Works

1. Set distance to start vertex = 0; all others = ∞.
2. Add all vertices to an unvisited set.
3. Pick the unvisited vertex with smallest known distance.
4. For each neighbor: if going through current vertex gives shorter distance, update it.
5. Mark current vertex as visited. Repeat until destination is reached.

Edge List Format

Enter edges as: 1-2:4, 1-3:2, 2-4:5, 3-4:1

This means:

• Edge between 1 and 2 with weight 4
• Edge between 1 and 3 with weight 2
• Edge between 2 and 4 with weight 5
• Edge between 3 and 4 with weight 1

Complexity

With a simple array: O(V²) where V = number of vertices. With a priority queue: O((V + E) log V) — much faster for sparse graphs.

Real-World Applications

• GPS navigation: finding the fastest route between two locations
• Internet routing: finding the shortest network path for data packets
• Flight paths: minimizing layover time or flight distance
• Game AI: pathfinding for characters in maps and mazes

Important Limitation

Dijkstra’s algorithm does NOT work with negative edge weights. For graphs with negative weights, use the Bellman-Ford algorithm instead.