Weighted vs unweighted
Overview
A weight is a real cost (like distance, time, or price) assigned to an edge. When graphs have weights, they are called weighted graphs. Unweighted graphs treat every edge identically, implicitly assigning each connection a cost or distance of exactly 1 unit. In an undirected vs directed context, weights apply to the specific direction of the edge. For an undirected weighted edge, the cost is the same in both directions. The moment weights exist, the fewest-edges path is no longer guaranteed to be the lowest-cost path.
Recognizing whether a problem involves uniform costs or variable costs is the deterministic first step in selecting a resolution algorithm. Weighted graphs fundamentally alter the definition of a shortest path.
Where used: Flight pricing graphs where edges are ticket costs, Map routing where edges are driving times
Why learn this
- The moment weights exist, fewest-edges does not mean lowest-cost.
- Applying an unweighted algorithm to a weighted graph (or vice versa) guarantees incorrect outputs or introduces massive unnecessary computational overhead.
Common mistakes
- Assuming fewest edges means shortest path in weighted graphs: A path of five edges each costing 1 is mathematically 'shorter' than a single edge costing 10. Minimizing edge count is not the same as minimizing total weight.
- Applying standard unweighted shortest path algorithms to weighted graphs: Unweighted shortest path algorithms (like standard BFS) rely on edge count. Using them on weighted graphs will find the path with the fewest hops, which is often not the cheapest path.
Recall questions
- What does an unweighted graph imply about edge costs?
- How does adding weights change the definition of a shortest path?
Understanding checks
In a graph, Path A has 1 edge with weight 10. Path B has 3 edges with weight 2 each. Which path is shorter in a weighted context, and which has fewer edges?
Path B is shorter in a weighted context (cost 6 vs 10). Path A has fewer edges (1 vs 3).
Weights shift the goal from minimizing hop count to minimizing cumulative cost. The path with the fewest edges is no longer guaranteed to be the cheapest.
You are building a friend-recommendation system finding the 'closest' connection based purely on degrees of separation. Is this graph weighted or unweighted?
Unweighted.
Degrees of separation just counts the number of hops (edges) between people. Every connection is treated identically, meaning uniform costs.
Practice tasks
Parse a weighted edge list
Modify this graph builder to handle weighted edges given as tuples of `(u, v, weight)` instead of unweighted `(u, v)`. The adjacency list should store tuples of `(neighbor, weight)`.
Continue learning
Previous: Graph representations
Next: When BFS Stops Working