Technology

Dijkstra's Algorithm: Finding the Shortest Path

December 06, 2025•

4 min read

Imagine you're in a city and want to get from point A to point B as fast as possible. You don't just want any path; you want the shortest one. That's exactly what Dijkstra's algorithm handles. It is the fundamental logic sitting underneath many GPS systems and network routing protocols.

At its core, Dijkstra is a "greedy" algorithm. It doesn't try to be clever by looking far ahead; instead, it systematically explores the closest unvisited options first, expanding outward like a ripple in a pond until it finds the target.

How It Actually Works

Here is the mental model without the math jargon:

Start at the Source: You stand at your starting node. The distance to yourself is 0. The distance to everywhere else is effectively infinity (because we don't know how to reach them yet).

Look at Neighbors: Check all the immediate neighbors of where you currently are. Calculate the distance to them from the start.

Update Records: If you found a shorter way to reach a neighbor than what you knew before, update your records.

Pick the Best Option: From all the unvisited nodes you know about, move to the one that is closest to the start. This is the "greedy" part.

Repeat: Treat that new node as your current spot and repeat the process until you've visited every reachable node.

Visualizing the Graph

Here is what our example graph looks like. The arrows represent the paths you can take, and the numbers are the "cost" (distance/time) to travel them.

Step-by-Step Execution

Let's trace the algorithm starting from node A.

Initialization:

Distances: A: 0, B: ∞, C: ∞, D: ∞

Priority Queue: [(0, A)]

Step 1: Processing Node A

Current node: A (distance 0)

Neighbors:

B: 0 + 1 = 1 (New shortest path!)

C: 0 + 4 = 4 (New shortest path!)

Queue: [(1, B), (4, C)]

Step 2: Processing Node B

Current node: B (distance 1) - Popped from queue

Neighbors:

C: 1 + 2 = 3. Current is 4. 3 < 4, so we update C.

D: 1 + 5 = 6. Current is ∞. Update D.

A: Already visited/shorter.

Queue: [(3, C), (4, C), (6, D)]

Step 3: Processing Node C

Current node: C (distance 3) - Popped from queue (priority 3)

Neighbors:

D: 3 + 1 = 4. Current is 6. 4 < 6, so we update D.

A, B: Already visited/shorter.

Queue: [(4, D), (4, C), (6, D)]

Step 4: Processing Node D

Current node: D (distance 4)

Neighbors: B, C (All visited or not shorter).

Queue is empty (ignoring stale entries).

Done!

Python Implementation

We use a priority queue (heap) here because it's incredibly efficient at always giving us the "next closest node" without us having to sort the entire list every time.

import heapq
def dijkstra(graph, start):
    # Track the shortest distance to each node.
    # We start with infinity for everyone except the start node.
    distances = {node: float('inf') for node in graph}
    distances[start] = 0
    
    # The priority queue holds tuples of (current_distance, node_name).
    # It automatically keeps the smallest distance at the top.
    pq = [(0, start)]
    
    while pq:
        # Pop the node with the smallest distance
        current_dist, current_node = heapq.heappop(pq)
        
        # Optimization: If we found a shorter path to this node effectively
        # "after" adding this entry to the queue, we can skip it.
        if current_dist > distances[current_node]:
            continue
        
        # Explore neighbors
        for neighbor, weight in graph[current_node].items():
            distance = current_dist + weight
            
            # Relaxation step: strictly better path found?
            if distance < distances[neighbor]:
                distances[neighbor] = distance
                heapq.heappush(pq, (distance, neighbor))
                
    return distances
# Let's test it out with a simple graph
graph = {
    'A': {'B': 1, 'C': 4},
    'B': {'A': 1, 'C': 2, 'D': 5},
    'C': {'A': 4, 'B': 2, 'D': 1},
    'D': {'B': 5, 'C': 1}
}
# Calculate shortest paths from 'A'
shortest_paths = dijkstra(graph, 'A')
print(shortest_paths)
# Output: {'A': 0, 'B': 1, 'C': 3, 'D': 4}

A Couple of Gotchas

While Dijkstra is powerful, it isn't magic. It assumes that edge weights are non-negative. If you have a graph where moving between nodes effectively "subtracts" distance (negative weights), Dijkstra can get stuck in loops or give wrong answers. For those specific cases, you'd want to look at the Bellman-Ford algorithm instead.

BlogSansar