Dijkstra's Algorithm: A Simple Visual Guide

What is Dijkstra's Algorithm?

Imagine you are in a city and want to get from Point A (your home) to Point B (a coffee shop) as quickly as possible. There are many roads, and each road takes a different amount of time to travel due to traffic or distance.

Dijkstra's Algorithm (pronounced "DIKE-stra") is a method for finding the shortest paths between nodes in a graph. It was conceived by computer scientist Edsger W. Dijkstra in 1956.

It is specifically designed for graphs with non-negative edge weights. If you have negative weights (like a "time travel" road that gains you time), you would need the Bellman-Ford algorithm instead.

How It Works (The "Greedy" Logic)

Dijkstra works on a "greedy" principle: Always visit the closest unvisited node next.

Step-by-Step Visualization

Let's find the shortest path from Node A to Node C.

   (A) --4--> (B)
    |          |
    2          1
    |          |
    v          v
   (D) --3--> (C)
                    

Step 1: Start at A

• A is 0.
• B is ∞. C is ∞. D is ∞.
• Current Node: A.

Step 2: Check Neighbors of A

• Neighbor B: Path A→B cost is 4. (4 < ∞, so update B to 4).
• Neighbor D: Path A→D cost is 2. (2 < ∞, so update D to 2).
• Mark A as visited.
• Unvisited Queue: D (2), B (4), C (∞).

Step 3: Pick Smallest (D)

• Logic: D has value 2, which is smaller than B's 4.
• Check D's neighbors: Only C (via D→C).
• Path A→D→C cost is 2 + 3 = 5. (5 < ∞, so update C to 5).
• Mark D as visited.
• Unvisited Queue: B (4), C (5).

Step 4: Pick Smallest (B)

• Logic: B has value 4.
• Check B's neighbors: Only C (via B→C).
• Path A→B→C cost is 4 + 1 = 5.
• Is 5 smaller than C's current value (5)? No. Do nothing.
• Mark B as visited.

Result

The shortest path to C is distance 5. (Both A→D→C and A→B→C cost 5 in this example).

Python Implementation

Here is a clean, production-ready implementation using Python's `heapq` module (Priority Queue) for efficiency.

import heapq

def dijkstra(graph, start):
    # Initialize distances: start is 0, others are infinity
    distances = {node: float('infinity') for node in graph}
    distances[start] = 0
    
    # Priority queue to store (distance, node) to visit next
    # We start with the source node
    pq = [(0, start)]
    
    while pq:
        # Get the node with the smallest distance
        current_distance, current_node = heapq.heappop(pq)
        
        # If we found a shorter path to this node already, skip
        if current_distance > distances[current_node]:
            continue
        
        # Check neighbors
        for neighbor, weight in graph[current_node].items():
            distance = current_distance + weight
            
            # If shorter path found
            if distance < distances[neighbor]:
                distances[neighbor] = distance
                heapq.heappush(pq, (distance, neighbor))
                
    return distances

# Example Graph (Adjacency List)
graph = {
    'A': {'B': 4, 'D': 2},
    'B': {'C': 1},
    'C': {},
    'D': {'C': 3}
}

print(dijkstra(graph, 'A'))
# Output: {'A': 0, 'B': 4, 'C': 5, 'D': 2}

Time Complexity

Where V is Vertices (Nodes) and E is Edges.

Applications in Real Life

• Google Maps: Finding the fastest route driving route (edges are roads, weights are travel times).
• Network Routing (OSPF): Sending data packets over the most efficient path in the internet.
• Social Networks: Finding the "degrees of separation" between two users.