Dijkstra grows a set of settled cities, always expanding the unsettled city with smallest distance. A min-heap makes “smallest distance” Θ(log n) instead of a scan.

Goal

Compute kilometres from Nairobi to Eldoret on a tiny road map.

The loop

import heapq

graph = {
    "Nairobi": [("Nakuru", 160), ("Mombasa", 480)],
    "Nakuru": [("Nairobi", 160), ("Eldoret", 160), ("Kisumu", 180)],
    "Mombasa": [("Nairobi", 480), ("Kisumu", 550)],
    "Kisumu": [("Nakuru", 180), ("Mombasa", 550)],
    "Eldoret": [("Nakuru", 160)],
}

def dijkstra(graph, start):
    dist = {start: 0}
    pq = [(0, start)]
    while pq:
        d, node = heapq.heappop(pq)
        if d != dist.get(node, d):
            continue
        for nbr, w in graph[node]:
            nd = d + w
            if nbr not in dist or nd < dist[nbr]:
                dist[nbr] = nd
                heapq.heappush(pq, (nd, nbr))
    return dist

print(dijkstra(graph, "Nairobi"))

Nairobi → Nakuru → Eldoret is 320 km, cheaper than anything through Mombasa.

From a file

Download edges.csv, Add files, then:

import csv
import heapq
from collections import defaultdict
from pathlib import Path

graph = defaultdict(list)
with Path("edges.csv").open(encoding="utf-8", newline="") as handle:
    for row in csv.DictReader(handle):
        graph[row["from"]].append((row["to"], int(row["km"])))

def dijkstra(graph, start):
    dist = {start: 0}
    pq = [(0, start)]
    while pq:
        d, node = heapq.heappop(pq)
        if d != dist.get(node):
            continue
        for nbr, w in graph[node]:
            nd = d + w
            if nd < dist.get(nbr, nd + 1):
                dist[nbr] = nd
                heapq.heappush(pq, (nd, nbr))
    return dist

print(dict(dijkstra(graph, "Nairobi")))

Pitfall

Negative kilometres break Dijkstra. This map has none. BFS is wrong here — hops ≠ kilometres (Nairobi–Mombasa is one hop and 480 km).