GraphsData structureaka edge-weighted graph, network

Weighted Graph

A graph whose edges carry numeric weights (cost, distance, capacity), so path length is a sum of weights rather than a hop count.

▶ Visualize Pattern: Shortest Path (Weighted)Practice (3)

Progress

Definition

A weighted graph attaches a number w(u, v) to every edge. The weight may model distance, time, cost, capacity, or probability. The length of a path is the sum of its edge weights, and "shortest path" means minimum total weight — which is no longer what plain Breadth-First Search (BFS) computes.

The choice of algorithm hinges on the weights: non-negative weights → Dijkstra's Algorithm; weights in {0, 1} → 0-1 BFS; negative weights allowed → Bellman-Ford; all-pairs on a dense graph → Floyd-Warshall; minimum total weight connecting everything → Kruskal's Algorithm or Prim's Algorithm.

In an Adjacency List each entry becomes a pair (neighbor, weight); in an Adjacency Matrix the cell holds the weight with ∞ (or a sentinel) for "no edge". Weights can live on directed or undirected edges.

edge weightsshortest pathMSTnegative weightsDijkstra

Intuition

A mental model before the formal terms.

A road map with distances written on each road. The fewest roads between two cities is not the shortest drive: three short country lanes can beat one long highway. Any algorithm that counts hops is answering the wrong question.

Dijkstra is like pouring water into the source: it spreads outward and reaches each city exactly when the shortest route arrives. That picture only works if no road has "negative length" — otherwise water could arrive, leave, and come back earlier.

How it works

Adjacency list of pairs: adj[u] = [(v, w), …]. For undirected graphs add (v, w) to adj[u] and (u, w) to adj[v].
Single-source shortest paths with non-negative weights: Dijkstra's Algorithm with a Min-Heap keyed on tentative distance, O((V + E) log V).
Negative weights: Bellman-Ford relaxes all edges V - 1 times, O(VE), and detects negative cycles with one more pass.
All pairs: Floyd-Warshall on the matrix, O(V³), or run Dijkstra from each vertex on sparse graphs.
Minimum spanning tree (undirected): Kruskal's Algorithm sorts edges and unions endpoints; Prim's Algorithm grows from a vertex with a heap.
Store weights in the edge structure, never in the vertex; a vertex weight can be converted to edge weights by adding it to every outgoing edge.

Why it works

Dijkstra's correctness relies on non-negative weights: once a vertex is popped with distance d, no later path can be shorter because every remaining path already has length ≥ d and can only grow.

Bellman-Ford works because any shortest path has at most V - 1 edges; after k rounds all shortest paths of ≤ k edges are final.

Kruskal's cut property: the minimum-weight edge crossing any cut belongs to some MST, so greedily adding the lightest non-cycle edge is always safe.

Operations

Operation	Description	Cost
addEdge(u, v, w)	Append (v, w) to adj[u] (and the reverse for undirected).	O(1)
weight(u, v)	Scan adj[u] for v (O(1) with a matrix).	O(deg(u))
updateWeight(u, v, w)	Find the entry and overwrite.	O(deg(u))
shortestPaths(s)	Dijkstra with a heap (non-negative weights).	O((V + E) log V)
shortestPathsNeg(s)	Bellman-Ford.	O(VE)
allPairs()	Floyd-Warshall.	O(V³)
mst()	Kruskal (E log E) or Prim (E log V).	O(E log V)

Recognition

How to tell a problem wants this.

Words like "cost", "distance", "time", "price", "capacity", "toll", "effort" attached to connections.
Input edges are triples [u, v, w].
"Cheapest", "minimum cost", "shortest time", "minimum spanning", "connect all points at minimum cost".
If all weights are equal, drop back to BFS; if weights are 0/1, use 0-1 BFS.

“weighted graph” → Shortest Path (Weighted)“connected groups” → Union-Find “maximum number of non-overlapping” → Greedy

Interactive demo

Play, step, change the input. ← → and space work too.

Showing the closely related Dijkstra's Algorithm visualization.

Weighted graph — One edge per line: "A B 4". Optional "source: A" / "target: F" lines.

Priority queue (min first)

node	dist
A	0

1/22All distances start at ∞ except dist[A] = 0. The priority queue always hands us the closest unsettled node, which is what makes greedy settling correct with non-negative weights.

Settled now (popped)In priority queueSettledEdge being relaxedBest-known parent edgeShortest path

PseudocodeLearn Dijkstra's Algorithm →

1dist = {v: ∞}; dist[source] = 0; pq = [(0, source)]
2while pq not empty:
3  (d, u) = pq.pop_min()
4  if d > dist[u]: continue   # stale entry
5  for (v, w) in neighbors(u):
6    if dist[u] + w < dist[v]:
7      dist[v] = dist[u] + w; parent[v] = u
8      pq.push((dist[v], v))
9path = follow parent from target back to source

Complexity

best O(V log V)

avg O((V + E) log V)

worst O((V + E) log V)

space O(V + E)

Speed

Pseudocode

1adj[u] = list of (v, w)
2dijkstra(s): dist = [inf]*V; dist[s] = 0; heap = [(0, s)]
3  while heap: d, u = pop; if d > dist[u]: continue
4    for v, w in adj[u]: if d + w < dist[v]: dist[v] = d + w; push (dist[v], v)
5mst_kruskal(): sort edges by w; dsu = UnionFind(V)
6  for u, v, w in edges: if dsu.union(u, v): total += w

Implementation

1import heapq
2import math
3 
4 
5class WeightedGraph:
6    """A weighted graph stores a cost with every edge, which is what turns
7    "fewest hops" into "cheapest path" and makes BFS insufficient."""
8 
91 · State: adj[u] holds (neighbour, weight) tuples
10    def __init__(self, n: int, directed: bool = False) -> None:
11        self.adj: list[list[tuple[int, float]]] = [[] for _ in range(n)]
12        self.directed = directed
13 
142 · The weight rides along with the endpoint in both stored half-edges
15    def add_edge(self, u: int, v: int, w: float) -> None:
16        self.adj[u].append((v, w))
17        if not self.directed and u != v:
18            self.adj[v].append((u, w))
19 
20    def __len__(self) -> int:
21        return len(self.adj)
22 
23    def neighbours(self, u: int) -> list[tuple[int, float]]:
24        return self.adj[u]
25 
263 · Total weight: halve it for undirected graphs, since edges are doubled
27    def total_weight(self) -> float:
28        total = sum(w for row in self.adj for _, w in row)
29        return total if self.directed else total / 2
30 
314 · Dijkstra: weights are why a priority queue replaces the BFS queue
32    def shortest_from(self, src: int) -> list[float]:
33        dist = [math.inf] * len(self.adj)
34        dist[src] = 0
35        pq: list[tuple[float, int]] = [(0, src)]
36        while pq:
37            d, u = heapq.heappop(pq)
38            if d > dist[u]:
39                continue  # stale entry, already improved
40            for v, w in self.adj[u]:
41                if d + w < dist[v]:
42                    dist[v] = d + w
43                    heapq.heappush(pq, (dist[v], v))
44        return dist
45 
465 · Negative weights break Dijkstra; detect them before choosing
47    def has_negative_weight(self) -> bool:
48        return any(w < 0 for row in self.adj for _, w in row)

Walkthrough

heapq does the whole job: heappush and heappop over a plain list, with tuples ordering lexicographically by distance first.
math.inf is the unreachable sentinel; math.inf + w is still math.inf, so relaxation against it can never succeed.
d, u = heapq.heappop(pq) unpacks the tuple directly, and the if d > dist[u]: continue guard skips stale entries.
for v, w in self.adj[u] unpacks each (neighbour, weight) tuple in the loop header, which is why tuples are preferred over a class here.
sum(w for row in self.adj for _, w in row) is a nested generator expression — one pass, no intermediate list.

Complexity (this implementation)

time O((V + E) log V) for Dijkstra with a binary heap · space O(V + E) storage, O(E) worst case for the heap with lazy deletion

heapq runs its sift loops in C, so this is one of the few graph algorithms where the Python version is not dramatically slower than the C++ one.

Language notes

heapq is a min-heap, the opposite default from std::priority_queue — porting Dijkstra between C++ and Python is exactly where that bites.
Tuple comparison is lexicographic, so (dist, vertex) sorts by distance and breaks ties by vertex id deterministically; a tie on both would then compare a third element, which is why non-comparable payloads must never be pushed.
math.inf is a float, so dist is a list[float] even for integer weights; use a large integer sentinel if exact integer arithmetic matters.
networkx.dijkstra_path_length and scipy.sparse.csgraph.dijkstra are the library answers for real workloads.

Common mistakes in this language

Pushing (dist, vertex, some_object) where the object is not comparable, which raises TypeError the moment two entries tie on distance and vertex.
Using float("inf") for distances and then comparing with == against an integer sentinel elsewhere in the code.
Running Dijkstra with negative weights — heapq will not complain, and the answer is silently wrong.

Language differences that matter here

Heap availability drives the whole implementation: Python has heapq and C++ has std::priority_queue, so Dijkstra is a dozen lines there; JavaScript and TypeScript must ship a binary heap inline, which is most of the code above.
Heap orientation is inverted between the two that have one — heapq is a min-heap, std::priority_queue is a max-heap needing std::greater — and this is the classic porting bug.
The infinity sentinel is cleanest in the dynamic languages: Infinity and math.inf saturate under addition, while C++ needs max/4 headroom to keep d + w from overflowing.
Edge payloads: C++ and Python use pairs/tuples that unpack in the loop header, TypeScript prefers a named interface for the edge and a positional tuple for the heap item, and JavaScript uses object literals for both.

Complexity

Operation	Average	Worst	Note
Access	O(1)	O(1)	Vertex by id.
Search	O(deg(u))	O(V)	Edge (u, v) lookup by scanning u's list.
Insert	O(1)	O(1)	Append an edge.
Delete	O(deg(u))	O(V)	Remove an edge from u's list.
Update	O(deg(u))	O(V)	Find the edge, then change its weight.
Shortest path (Dijkstra)	O((V + E) log V)	O((V + E) log V)	Non-negative weights.
Shortest path (Bellman-Ford)	O(VE)	O(VE)
All pairs (Floyd-Warshall)	O(V³)	O(V³)
MST	O(E log V)	O(E log V)
Space	O(V + E)

Advantages & disadvantages

Advantages

Models real costs: distances, latencies, prices, capacities.
Rich, well-understood algorithm toolbox for shortest paths, MST, and flow.
Same representations as unweighted graphs with one extra field per edge.

Disadvantages

Plain BFS no longer gives shortest paths; algorithms are O(E log V) or worse.
Negative weights break Dijkstra and negative cycles make "shortest path" undefined.
Floating-point weights introduce comparison and accumulation errors.

Use cases

Navigation and routing: shortest driving time between locations.
Network routing protocols (OSPF uses Dijkstra).
Minimum-cost wiring, pipelines, and cluster connections (MST).
Cheapest flights with at most k stops (Bellman-Ford variant / BFS with pruning).
Currency arbitrage: negative cycles on -log(rate) weights.

Use it when

Edges have different costs and the objective sums them.
Shortest/cheapest path, minimum spanning tree, max flow, bottleneck path.
Weights are non-negative → Dijkstra; negative → Bellman-Ford; dense all-pairs → Floyd-Warshall.

Avoid it when

All edges cost the same — use an Unweighted Graph with BFS, O(V + E).
Weights are only 0 and 1 — 0-1 BFS with a deque is linear.
The "weight" is on vertices and is uniform — still an unweighted problem.

Alternatives

Unweighted Graph Adjacency Matrix Edge List Directed Graph

Common mistakes

Running BFS and expecting the minimum-weight path.
Using Dijkstra with negative edge weights — it silently returns wrong answers.
Not skipping stale heap entries (if d > dist[u]: continue), turning Dijkstra into O(E²) in the worst case.
Forgetting to add the reverse (u, w) entry on undirected edges.
Using 0 or -1 as "no edge" in a matrix when a real weight could be 0 or negative — use ∞/null.

Interview patterns

Network Delay Time: Dijkstra from the source, answer is the max distance.
Cheapest Flights Within K Stops: Bellman-Ford limited to k+1 rounds, or BFS with per-level relaxation.
Min Cost to Connect All Points: Prim/Kruskal on an implicit complete graph.
Path With Minimum Effort / bottleneck path: Dijkstra on max-edge-so-far, or binary search + BFS.
Swim in Rising Water: Dijkstra with max instead of +.

Interview questions on this

Choosing between BFS, DFS, Dijkstra and DPAdvanced
Choosing a shortest-path algorithmAdvanced
Greedy or dynamic programming?Advanced
Union-Find or DFS for connectivity?Advanced

Mock interviews

Network Delay TimeAdvanced
Number of IslandsIntermediate
Merge IntervalsIntermediate

Interview problems

Network Delay Timemedium Cheapest Flights Within K Stopsmedium Min Cost to Connect All Pointsmedium

Definition

Intuition

How it works

Why it works

Operations

Recognition

Interactive demo

Pseudocode

Implementation

Complexity

Advantages & disadvantages

Use cases

Alternatives

Common mistakes

Interview patterns

Interview problems

Related