Dijkstra's Algorithm

A single-source shortest path algorithm for graphs with non-negative edge weights.

What is Dijkstra's Algorithm?

Dijkstra's algorithm is a greedy algorithm that solves the single-source shortest path problem for a directed or undirected graph with non-negative edge weights. This algorithm was conceived by computer scientist Edsger W. Dijkstra in 1956 and published three years later.

Key Features

Finds the shortest path from a start node for all other nodes in a graph
Works only with non-negative edge weights (see reference link for more info on why)
Employs a greedy approach, always choosing the next unvisited node with the smallest distance
Has a time complexity of O(V²) with an adjacency matrix, or O((V+E)log V) with a min-heap-based priority queue

Algorithm Steps

Initialize distances of all vertices as infinite and distance of source vertex as 0
Add all vertices to an unvisited set
While the unvisited set is not empty:
- Pick the vertex with the minimum distance
- Update distances to adjacent vertices using distance of current vertex
- Mark the vertex as visited
Return all shortest distances from source

Visualization of how Dijkstra's algorithm explores a graph, with visited nodes in red and shortest distances in blue.

Credit to Wikimedia Commons

Interactive Demo

This interactive demo shows Dijkstra's algorithm in action. Click on nodes to set the start and end points, then click "Run Algorithm" to visualize the shortest path finding process.

First click: Set start node (green) | Second click: Set end node (red)

Pseudocode

function Dijkstra(Graph, source):
    dist[source] = 0
    for each vertex v in Graph:
        if v is not the source
            dist[v] = inf
        add v to unvisited

    while unvisited is not empty:
        u = vertex in unvisited with min dist
        remove u from unvisited
        
        for each neighbor v of u:
            alt = dist[u] + length(u, v)
            if alt < dist[v]:
                dist[v] = alt
                prev[v] = u
    
    return dist list, prev list

Time Complexity Analysis

The time complexity of Dijkstra's algorithm depends on the data structure used:

Using an array: O(V²) - suitable for dense graphs
Using a binary heap: O((V+E)log V) - better for sparse graphs
Using a Fibonacci heap: O(E + V log V) - theoretically optimal

where V is the number of vertices and E is the number of edges in the graph.

Additional Notes

Dijkstra's algorithm doesn't work with negative weight edges
For negative weights, use the Bellman-Ford algorithm instead
A* algorithm is an extension of Dijkstra's that uses heuristics to improve performance, commonly used for autonomous agent pathfinding
In practice, optimizations like bidirectional search can significantly speed up pathfinding

Applications

Network Routing

Used in routing protocols like OSPF (Open Shortest Path First) to find the most efficient path for data packets.

GPS Navigation

Powers navigation systems to find the shortest route between locations on a map.

Social Networks

Used to analyze social graphs and find the shortest connection between users.