Weighted graphs

BFS finds the shortest path between two nodes by hop count: every edge costs 1. Real networks rarely work that way. A road between cities may be much longer than another; a network link may have higher latency. Once edges carry weights, BFS can return a path with fewer hops that is actually longer in total cost.

Representing weights in an adjacency list

Unweighted adjacency list:

graph = {
    0: [1, 2],
    1: [3],
    2: [1, 3],
    3: [],
}

Weighted adjacency list — each neighbour becomes a (neighbour, weight) tuple:

graph = {
    0: [(1, 4), (2, 1)],
    1: [(3, 1)],
    2: [(1, 2), (3, 5)],
    3: [],
}

Edge 0 → 2 costs 1; 2 → 1 costs 2; so the path 0 → 2 → 1 → 3 totals 1 + 2 + 1 = 4. The direct edge 0 → 1 costs 4 alone. BFS would report 0 → 1 as a "one-hop" shortest path, missing the cheaper three-hop route.

Why BFS fails

BFS explores nodes in order of hop distance. It marks a node as visited the first time it is reached, which is correct when all edges have equal weight. With unequal weights, the first path found to a node may not be the cheapest. You would need to revisit nodes to see whether a longer-hop route is cheaper in total — which BFS cannot do without significant modification.

Relaxation

The core idea behind efficient shortest-path algorithms is relaxation. Maintain a distance estimate dist[v] for every node, initialised to infinity except dist[source] = 0. When you examine edge (u, v, w), ask: is dist[u] + w < dist[v]? If so, you have found a cheaper route to v through u — update dist[v]. Repeat until no estimate can be improved.

# One relaxation step
if dist[u] + weight(u, v) < dist[v]:
    dist[v] = dist[u] + weight(u, v)

Different algorithms differ in which edges they relax and in what order:

• Bellman-Ford relaxes every edge repeatedly — O(VE), handles negative weights.
• Dijkstra's relaxes edges greedily, always extending the cheapest known path first using a priority queue — O((V + E) log V), requires non-negative weights.

Where to go next

Next: Dijkstra's algorithm — a complete implementation using Python's heapq, returning shortest distances from a source to every node, plus a helper to reconstruct the actual path.