ZERO / HERO
Roads have lengths

Weighted Graphs & Representations

The analogy

Until now every road took the same effort to walk. Real maps are not like that: some roads are motorways and some are muddy tracks. Once edges have costs, "fewest roads" and "shortest journey" stop being the same question — and the tool that answered the first one stops working.

Visualizer

Roads with costs

step 1 / 6
ABCDEF

Six towns, eight roads — and now the roads have lengths. A-C is 2, A-B is 4, B-D is 10.weights: A-B 4, A-C 2, B-C 5, B-D 10, C-E 3, E-D 4, D-F 11, E-F 5

from collections import defaultdict

# adjacency list — O(V + E), right for sparse graphs
g = defaultdict(list)
def add_edge(u, v, w, directed=False):
    g[u].append((v, w))
    if not directed:
        g[v].append((u, w))    # do not forget this

# adjacency matrix — O(V^2), O(1) edge lookup
INF = float("inf")
m = [[INF] * n for _ in range(n)]
m[u][v] = w

# edge list — for Kruskal / Bellman-Ford
edges = [(w, u, v), ...]

# BFS gives fewest EDGES. Weighted shortest path needs Dijkstra.
Check yourself

All edges are weighted 1 except one weighted 100. Does BFS find the cheapest path?