Dijkstra's Shortest Path Algorithm

Introduction

Dijkstra's algorithm computes the shortest paths from a single source vertex to all other vertices in a weighted graph. It operates by maintaining a set of visited nodes and iteratively selecting the unvisited node with the smallest known distance from the source, updating the distances of its neighbors accordingly.

The algorithm is particularly notable for its greedy approach: at each step, it makes the locally optimal choice with the hope of finding a global optimum. While efficient, it has a critical limitation—it cannot handle graphs with negative edge weights.

How It Works

The algorithm maintains two primary data structures:

Distance Array: Stores the current shortest known distance from the source to each vertex. Initialized to infinity, except for the source (set to 0).
Priority Queue: Efficiently retrieves the unvisited vertex with the minimum distance. Typically implemented as a binary heap or Fibonacci heap.

At each iteration, the algorithm extracts the vertex with the smallest tentative distance, marks it as visited, and relaxes its outgoing edges. If a shorter path to a neighbor is found, the neighbor's distance is updated and it's re-inserted into the priority queue.

Pseudocode

function Dijkstra(Graph, source):
    for each vertex in Graph:
        vertex.distance = ∞
        vertex.visited = false
        vertex.predecessor = null

    source.distance = 0
    priority_queue = new MinHeap()
    priority_queue.push(source, 0)

    while priority_queue is not empty:
        current = priority_queue.pop()
        if current.visited: continue
        current.visited = true

        for each neighbor in current.adjacent:
            alt = current.distance + weight(current, neighbor)
            if alt < neighbor.distance:
                neighbor.distance = alt
                neighbor.predecessor = current
                priority_queue.push(neighbor, alt)

    return distances, predecessors

Step-by-Step Example

Consider a simple graph with vertices A, B, C, D and edges: A→B (4), A→C (2), B→C (1), B→D (5), C→D (8). Starting from A:

Step	Visited	B	C	D
Init	-	∞	∞	∞
1	A	4	2	∞
2	C	4	2	∞
3	B	4	2	9
4	D	4	2	9

💡 Note: The algorithm guarantees optimal paths only when all edge weights are non-negative. Negative weights can cause infinite loops or incorrect results.

Time & Space Complexity

The efficiency of Dijkstra's algorithm depends heavily on the priority queue implementation:

Binary Heap: O((V + E) log V) time, O(V) space
Fibonacci Heap: O(E + V log V) time, O(V) space
Simple Array: O(V²) time, O(V) space (efficient for dense graphs)

Where V is the number of vertices and E is the number of edges.

Limitations & Alternatives

While powerful, Dijkstra's algorithm has notable constraints:

No Negative Weights: Fails with negative edges. Use the Bellman-Ford Algorithm instead.
Single-Source: Computes paths from one node. For all-pairs shortest paths, use Floyd-Warshall or Johnson's Algorithm.
Heuristic Guidance: For pathfinding in games/maps, A* Search incorporates heuristics to explore more efficiently.

Real-World Applications

Dijkstra's algorithm powers countless systems where optimal routing is critical:

🗺️ GPS & Navigation: Calculating fastest driving/walking routes
🌐 Network Routing: OSPF and IS-IS protocols in TCP/IP networks
🎮 Game Development: NPC pathfinding and procedural map navigation
🔗 Social Networks: Finding shortest connection chains between users
🏭 Logistics & Supply Chain: Optimizing delivery routes and warehouse layouts

Historical Context

Edsger W. Dijkstra conceived the algorithm in 1956 while working at the Mathematical Centre in Amsterdam. He designed it in just 20 minutes without pen or paper to demonstrate the capabilities of the ARMAC computer. The algorithm was formally published in 1959 in Numerische Mathematik.

Dijkstra later reflected on this achievement, noting it taught him the value of rigorous mathematical thinking in programming. His work laid foundational principles for modern algorithm design and formal verification.

References & Further Reading

Dijkstra, E. W. (1959). "A note on two problems in connexion with graphs." Numerische Mathematik, 1(1), 269–271.
Cormen, T. H., Leiserson, C. E., Rivest, R. L., & Stein, C. (2009). Introduction to Algorithms (3rd ed.). MIT Press.
Goodrich, M. T., Tamassia, R., & Goldwasser, M. H. (2014). Algorithm Design and Applications. Wiley.