BlogSansar

Technology

Dijkstra's Algorithm: Finding the Shortest Path

R
Rohan Shrestha
December 14, 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:
  1. 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).
  1. Look at Neighbors: Check all the immediate neighbors of where you currently are. Calculate the distance to them from the start.
  1. Update Records: If you found a shorter way to reach a neighbor than what you knew before, update your records.
  1. 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.
  1. 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: ∞, E: ∞
  • Priority Queue: [(0, A)]

Step 1: Processing Node A

  • Current node: A (distance 0)
  • Neighbors:
  • B: 0 + 2 = 2 (new shortest path)
  • C: 0 + 5 = 5 (new shortest path)
  • Queue: [(2, B), (5, C)]

Step 2: Processing Node B

  • Current node: B (distance 2) – popped from queue
  • Neighbors:
  • C: 2 + 1 = 3. Current best is 5 ⇒ update C.
  • D: 2 + 4 = 6. Current best is ∞ ⇒ update D.
  • A: already finalized.
  • Queue: [(3, C), (5, C), (6, D)]

Step 3: Processing Node C

  • Current node: C (distance 3) – popped with priority 3
  • Neighbors:
  • D: 3 + 2 = 5. Current best is 6 ⇒ update D.
  • E: 3 + 7 = 10. Current best is ∞ ⇒ update E.
  • A, B: already shorter.
  • Queue: [(5, D), (5, C), (6, D), (10, E)]

Step 4: Processing Node D

  • Current node: D (distance 5)
  • Neighbors:
  • E: 5 + 1 = 6. Current best is 10 ⇒ update E.
  • B, C: already finalized.
  • Queue: [(5, C), (6, D), (6, E), (10, E)]

Step 5: Processing Node E

  • Current node: E (distance 6)
  • Its only outgoing neighbor leads back to already shorter nodes.
  • Queue becomes 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 the graph above
graph = {
    'A': {'B': 2, 'C': 5},
    'B': {'A': 2, 'C': 1, 'D': 4},
    'C': {'A': 5, 'B': 1, 'D': 2, 'E': 7},
    'D': {'B': 4, 'C': 2, 'E': 1},
    'E': {'D': 1, 'A': 8},
}

# Calculate shortest paths from 'A'
shortest_paths = dijkstra(graph, 'A')
print(shortest_paths)
# Output: {'A': 0, 'B': 2, 'C': 3, 'D': 5, 'E': 6}

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.

Comments (0)

You