Dijkstra's Shortest Path Calculator

What is Dijkstra's Algorithm?

Dijkstra's algorithm is one of the most celebrated algorithms in computer science. Invented by Dutch computer scientist Edsger W. Dijkstra in 1956 and published in 1959, it solves the single-source shortest path problem for a weighted graph with non-negative edge weights. Given a starting (source) vertex, the algorithm computes the minimum-cost path from that source to every other vertex in the graph.

The algorithm is a classic example of a greedy strategy: at each step it selects the unvisited vertex with the currently smallest known distance, then uses that vertex to try to improve the known distances to its neighbours. This process is known as relaxation.

How Dijkstra's Algorithm Works

1. Initialise all distances to Infinity, except the source which is set to 0.
2. Mark all vertices as unvisited. Place all vertices in an unvisited set.
3. Select the unvisited vertex u with the smallest tentative distance.
4. For each unvisited neighbour v of u, compute alt = dist[u] + weight(u, v).
5. If alt < dist[v], update dist[v] = alt and record prev[v] = u.
6. Mark u as visited (remove from unvisited set).
7. Repeat from step 3 until all vertices are visited or the target is reached.

To reconstruct the path to any vertex, trace back through the prev[] array from the target to the source.

Dijkstra's Algorithm Example

Consider the Simple Network example with 5 nodes (A–E) and the following edges: A-B=4, A-C=2, B-C=1, B-D=5, C-D=8, C-E=10, D-E=2. Starting from A:

Step	Visiting	dist[A]	dist[B]	dist[C]	dist[D]	dist[E]
Init	—	0	∞	∞	∞	∞
1	A	0	4	2	∞	∞
2	C	0	3	2	10	12
3	B	0	3	2	8	12
4	D	0	3	2	8	10
5	E	0	3	2	8	10

Final shortest distances from A: B=3 (A→C→B), C=2 (A→C), D=8 (A→C→B→D), E=10 (A→C→B→D→E).

Time Complexity Analysis

Implementation	Time Complexity	Space	Best For
Array / naive	O(V²)	O(V)	Dense graphs
Binary heap	O((V + E) log V)	O(V + E)	Sparse graphs
Fibonacci heap	O(E + V log V)	O(V + E)	Theoretical optimum

This calculator uses the O(V²) array implementation, which is perfectly efficient for graphs with up to 15 nodes.

When to Use Dijkstra's vs Other Algorithms

Algorithm	Negative Weights	Single Source	All Pairs	Complexity
Dijkstra's	No	Yes	No	O(V² ) or O(E log V)
Bellman-Ford	Yes	Yes	No	O(VE)
Floyd-Warshall	Yes	No	Yes	O(V³)
A* Search	No	Yes (single target)	No	O(E log V) with heuristic
BFS	N/A (unweighted)	Yes	No	O(V + E)

Real-World Applications

• GPS Navigation: Finding the fastest or shortest route between two locations on a road network.
• Network Routing: Internet routers use variants of Dijkstra's (OSPF protocol) to determine the best path for data packets.
• Game Pathfinding: NPC characters in video games navigate terrain using Dijkstra's or its heuristic variant A*.
• Logistics & Supply Chain: Optimising delivery routes to minimise distance or cost.
• Social Networks: Finding the shortest chain of connections between two people (degrees of separation).
• Airline Route Planning: Computing the minimum-cost itinerary between two airports.