Dijkstra’s Shortest Path Algorithm

Definition

Dijkstra’s shortest path algorithm is a greedy graph algorithm used to compute the shortest path from a single source vertex to all other vertices in a weighted graph with non-negative edge weights.

In simple terms, it:

starts from one source node,
assigns distance 0 to the source and infinity to all others,
repeatedly selects the unvisited vertex with the smallest tentative distance,
and updates the distances of its neighbors if a shorter path is found.

It is called a single-source shortest path algorithm because it finds shortest paths starting from one chosen source vertex.

Main Content

1. Graph Representation and Key Terms

Weighted graph

Dijkstra’s algorithm works on graphs where each edge has a weight or cost. The weight may represent distance, time, money, or any measurable cost.

Non-negative edge weights

The algorithm requires all weights to be zero or positive. If negative weights exist, the greedy choice may become incorrect.

Important terms:

Source vertex

The starting vertex from which shortest paths are calculated.

Distance array

Stores the best known distance from the source to every vertex.

Visited/settled vertex

A vertex whose shortest distance has been finalized.

Tentative distance

A temporary shortest distance that may still be improved.

Example graph:

        2
    A ------ B
    | \      |
   4|  \1    |3
    |   \    |
    C ------ D
        5

If A is the source:

distance to A = 0
distance to B = 2
distance to C = 4
distance to D may be reached through A→B→D or A→C→D, and the algorithm will determine the minimum.

2. Greedy Strategy and Relaxation

Greedy choice

At each step, the algorithm selects the unvisited vertex with the smallest known distance from the source. This choice is safe because, with non-negative weights, no future path can produce a shorter route to that vertex.

Relaxation

When a vertex is selected, the algorithm checks all its adjacent edges and updates the distance of neighboring vertices if a shorter path is discovered.

Relaxation rule:

If distance[u] + weight(u, v) < distance[v], then update:
distance[v] = distance[u] + weight(u, v)

Why relaxation matters:

It gradually improves the estimated shortest distances.
It ensures all paths through the current vertex are properly considered.

Example: If the current shortest distance to B is 2 and edge B→D has weight 3, then the new possible distance to D is 5. If D already had distance 7, it gets updated to 5.

This process continues until all vertices are settled or no unvisited vertices remain reachable.

3. Correctness and Limitations

Correctness idea

Once a vertex is chosen as the minimum-distance unvisited vertex, its shortest path is fixed because any alternative route would have to pass through other unvisited vertices with equal or larger tentative distances, and non-negative weights cannot create a smaller path later.

Limitation with negative edges

Dijkstra’s algorithm does not work correctly when a graph contains negative edge weights. In such cases, a later path might reduce the cost unexpectedly, breaking the greedy logic.

Important points:

The algorithm is correct only for graphs with non-negative weights.
It can be used on directed or undirected graphs.
It does not find shortest paths if there are negative cycles or negative edges.

Simple illustration of failure with negative weights:

Suppose a vertex appears to have the shortest distance early,
but a later path with a negative edge could make it smaller,
Dijkstra would have already finalized the earlier value incorrectly.

So, for graphs with negative weights, algorithms like Bellman-Ford are preferred.

Working / Process

1. Initialize distances

Set the source vertex distance to 0.
Set all other vertex distances to infinity (∞).
Mark all vertices as unvisited.
Keep a predecessor array if the actual shortest path must be reconstructed.

2. Select the nearest unvisited vertex and relax edges

Choose the unvisited vertex with the smallest tentative distance.
Mark it as visited because its shortest distance is now finalized.
For each unvisited neighbor, calculate a new possible distance through the selected vertex.
If the new value is smaller, update the neighbor’s distance and record the predecessor.

3. Repeat until completion

Continue selecting the next closest unvisited vertex and relaxing its edges.
Stop when all vertices are visited or when the remaining vertices are unreachable.
Use the predecessor information to trace back the shortest path from any destination to the source.

Example trace:

Suppose the graph has:

A→B = 2
A→C = 4
B→C = 1
B→D = 7
C→D = 3

Start with A:

dist(A)=0, dist(B)=∞, dist(C)=∞, dist(D)=∞

After relaxing from A:

dist(B)=2
dist(C)=4

Pick B next because 2 is smallest:

Relax B→C: dist(C)=min(4, 2+1)=3
Relax B→D: dist(D)=9

Pick C next because 3 is smallest:

Relax C→D: dist(D)=min(9, 3+3)=6

Final shortest distances from A:

A = 0
B = 2
C = 3
D = 6

Shortest path to D:

A → B → C → D

Advantages / Applications

Efficient for non-negative weighted graphs

It quickly finds shortest paths without exploring every route, making it practical for large graphs.

Used in real-world navigation and networking

GPS systems, map applications, and router path selection use shortest path ideas similar to Dijkstra’s algorithm.

Foundation for advanced graph algorithms

It helps students understand greedy methods, relaxation, and shortest path techniques, and it is often used as a building block in more complex problems.

Common applications:

road and transport network routing
internet packet routing
game development pathfinding
robotics navigation
resource minimization problems
dependency and scheduling systems

Summary

Dijkstra’s algorithm finds the shortest path from one source vertex to all other vertices in a weighted graph.
It uses a greedy approach by repeatedly choosing the nearest unvisited vertex and relaxing its edges.
It works only when all edge weights are non-negative and is widely used in real-world routing and navigation.