Dijkstra's Algorithm — Shortest Path, Explained Simply

Imagine you're Google Maps. A user drops a pin from Delhi to Mumbai and hits "Get Directions." Behind the scenes, one of the most elegant algorithms in computer science quietly runs — evaluating hundreds of roads, intersections, and traffic weights — to hand back the fastest route in milliseconds.

That algorithm is Dijkstra's Shortest Path Algorithm, published by Dutch computer scientist Edsger W. Dijkstra in 1959. It's a staple of every DSA course, every competitive programming contest, and every real-world routing system. Today we break it down from scratch — no jargon overload, just clean logic and a working example.

What is Dijkstra's Algorithm?

Dijkstra's algorithm finds the shortest (minimum-weight) path from a single source node to all other nodes in a weighted graph. The key constraint: all edge weights must be non-negative. It does not work correctly with negative weights — use Bellman-Ford for those cases.

Where is it Used?

• 🗺️ GPS & Maps — Google Maps, Apple Maps, and OpenStreetMap all rely on Dijkstra variants
• 🌐 Network Routing — The OSPF protocol used by internet routers runs Dijkstra to find shortest data paths
• ✈️ Flight Booking — Cheapest flight route search between airports
• 🎮 Game AI — NPC pathfinding in games like Age of Empires
• 📦 Logistics — Delivery route optimisation

The Graph We'll Use

Let's define a weighted undirected graph with 6 nodes: A, B, C, D, E, F. We'll find the shortest path from node A to every other node.

Edge List

Step-by-Step Walkthrough

We initialise all distances to ∞ except source A which starts at 0. A min-heap priority queue always picks the node with the smallest tentative distance next.

Final Shortest Distances from A

• A → A 0
• A → B 3  (A → C → B)
• A → C 2  (A → C)
• A → D 8  (A → C → B → D)
• A → E 10  (A → C → B → D → E)
• A → F 13  (A → C → B → D → E → F)

The Algorithm — Pseudocode

function Dijkstra(graph, source):
    dist[source] = 0
    dist[all other nodes] = ∞
    priority_queue = [(0, source)]
    visited = {}

    while priority_queue is not empty:
        (current_dist, u) = pop minimum from priority_queue

        if u in visited → skip
        mark u as visited

        for each neighbor v of u with edge weight w:
            new_dist = current_dist + w
            if new_dist < dist[v]:
                dist[v] = new_dist
                push (new_dist, v) into priority_queue

    return dist

Python Implementation

import heapq

def dijkstra(graph, source):
    dist = {node: float('inf') for node in graph}
    dist[source] = 0

    pq = [(0, source)]   # (distance, node)
    visited = set()

    while pq:
        current_dist, u = heapq.heappop(pq)

        if u in visited:
            continue
        visited.add(u)

        for neighbor, weight in graph[u]:
            new_dist = current_dist + weight
            if new_dist < dist[neighbor]:
                dist[neighbor] = new_dist
                heapq.heappush(pq, (new_dist, neighbor))

    return dist


# ── Graph Definition ──
graph = {
    'A': [('B', 4), ('C', 2)],
    'B': [('A', 4), ('C', 1), ('D', 5)],
    'C': [('A', 2), ('B', 1), ('D', 8), ('E', 10)],
    'D': [('B', 5), ('C', 8), ('E', 2), ('F', 6)],
    'E': [('C', 10), ('D', 2), ('F', 3)],
    'F': [('D', 6), ('E', 3)],
}

result = dijkstra(graph, 'A')

print("Shortest distances from A:")
for node, distance in sorted(result.items()):
    print(f"  A → {node} : {distance}")

Output

Shortest distances from A:
  A → A : 0
  A → B : 3
  A → C : 2
  A → D : 8
  A → E : 10
  A → F : 13

Time & Space Complexity

For most real-world use cases the binary heap version — O((V+E) log V) — is the standard choice. It's exactly what Python's heapq gives you.

Limitations of Dijkstra

• ❌ Negative edges — algorithm breaks. Use Bellman-Ford instead.
• ❌ Negative cycles — undefined behaviour. Use Floyd-Warshall.
• ✅ Works perfectly for — non-negative weighted graphs, directed and undirected.

Dijkstra vs Other Shortest Path Algorithms

Quick Summary

• Finds shortest path from a single source to all nodes
• Uses a min-heap priority queue for efficiency
• Requires non-negative edge weights
• Time complexity: O((V+E) log V) with a binary heap
• Used in GPS, network routing (OSPF), game AI, and logistics

Found this helpful? Share it with your study group and bookmark Codenosis for more DSA breakdowns, Python tutorials, and real-world coding guides.