Once a graph has weights on its edges — think of road distances, flight costs, or network latency — "shortest path" no longer means "fewest edges." It means the path whose edges add up to the smallest total weight. This single shift changes which traversal algorithm you reach for, and it's the foundation behind route planners, network routing protocols, and countless optimization problems.

If you haven't yet, it helps to be comfortable with how graphs are represented and with basic BFS traversal before this one, since the algorithm here builds directly on BFS's "explore outward" idea but adds a cost-aware twist.

Why BFS Alone Doesn't Work for Weighted Graphs

Plain BFS finds the shortest path in terms of edge count, because it explores the graph in neat, expanding layers — everything one hop away, then everything two hops away, and so on. That guarantee completely falls apart once edges have different weights. A path with 4 cheap edges can easily beat a path with 2 expensive ones, and BFS has no way to account for that — it would happily report the 2-edge path as "shorter" even though it costs more.

Dijkstra's Algorithm, Conceptually

Dijkstra's algorithm fixes this with a simple, greedy idea: always expand the closest unvisited node next, where "closest" means lowest total cost from the start, not fewest hops. It keeps a running "best distance so far" for every node (starting at infinity, except 0 for the source), and a priority queue ordered by that distance so it always knows which node to process next.

import heapq

def dijkstra(graph, start):
    # graph: {node: [(neighbor, weight), ...]}
    distances = {node: float("inf") for node in graph}
    distances[start] = 0
    pq = [(0, start)]  # (distance, node)

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

        # Skip stale entries left behind by earlier relaxations
        if current_dist > distances[node]:
            continue

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

    return distances

graph = {
    "A": [("B", 4), ("C", 1)],
    "B": [("D", 1)],
    "C": [("B", 2), ("D", 5)],
    "D": [],
}

print(dijkstra(graph, "A"))

Output:

{'A': 0, 'B': 3, 'C': 1, 'D': 4}

Notice the algorithm found that A→C→B (cost 1+2=3) beats the direct A→B edge (cost 4) — exactly the kind of result plain BFS could never produce, since it would have only looked at hop counts.

Complexity and Limits

With a binary heap as the priority queue, Dijkstra runs in O((V + E) log V), where V is the number of vertices and E the number of edges — efficient enough for most real-world graphs. One important caveat: Dijkstra assumes all edge weights are non-negative. If your graph can have negative weights, you need a different algorithm (Bellman-Ford), because Dijkstra's greedy "never revisit a finalized node" assumption breaks down.

For a concrete, runnable version of this exact algorithm with step-by-step output, see the Dijkstra's algorithm program example.