Weighted Graphs and Costs

The Real World Has Costs

So far, we have treated every step as equal. Moving from one cell to its neighbor costs the same as any other move. But the real world is rarely so uniform.

Think about hiking through a forest. Walking along a flat trail is easy. Trudging through knee-deep mud takes more effort. Climbing a steep rocky slope is harder still. If you want to get from point A to point B with minimal effort, you might choose a longer route that avoids the difficult terrain.

This is the essence of weighted graphs. Each edge has a cost or weight associated with it. The weight might represent:

• Distance: Kilometers between cities on a road network
• Time: Minutes to traverse a road considering traffic
• Effort: Energy required to cross different terrain types
• Money: Fuel cost or toll fees along a route
• Risk: Probability of encountering danger

In our grid representation, we can assign weights to cells. Moving into a cell with weight 5 costs five times as much as moving into a cell with weight 1. The path that minimizes total cost might not be the path with the fewest steps.

BFS Doesn't Work Here

Breadth-first search finds the path with the fewest edges. It explores in order of distance, where distance is counted in steps. This is perfect when every step costs the same.

But when edges have different weights, BFS fails. It finds the path with the minimum number of steps, not the minimum total cost. These are very different things.

Consider a simple example: you need to cross a valley. The direct path goes straight across, but the valley floor is a swamp that costs 9 per cell. A path that goes around the ridge adds more steps but only costs 1 per cell. BFS will charge straight through the swamp, oblivious to the cost.

The failure is dramatic. BFS treats the expensive red cells (cost 9) exactly like the cheap green cells (cost 1). It counts edges, not costs. The result is a path that looks efficient but is actually wasteful.

This is not a bug in BFS—it is doing exactly what it was designed to do. BFS answers the question "what is the shortest path in terms of steps?" When we ask "what is the cheapest path in terms of cost?", we need a different algorithm.

Understanding Terrain Costs

Before we find better algorithms, let us build intuition for how costs change the problem. In the visualization below, you can paint different costs onto the terrain. Higher numbers mean more expensive terrain.

Experiment with creating barriers of expensive terrain. Notice that even a single row of high-cost cells can make a detour worthwhile. The key insight is that cheap does not mean short. A longer path through easy terrain can cost less than a short path through difficult terrain.

This is why hikers study topographic maps. A trail that winds around a mountain might be twice as long as going straight over, but requires a fraction of the effort. The direct path has fewer steps but costs more energy.

Visualizing Cost as Height

One powerful way to think about terrain costs is as elevation. Expensive terrain is like climbing a mountain—you can do it, but it costs more effort. Cheap terrain is like walking on flat ground.

When we see costs as heights, the optimal path becomes visually intuitive. Going around the mountain is clearly easier than going over it, even though the distance is greater. The cheapest path follows the valleys, avoiding the peaks.

This mental model—cost as elevation—is remarkably useful. It explains why algorithms that respect costs often find paths that seem to "flow" around obstacles like water finding the path of least resistance.

Setting Up for Dijkstra

We now understand the problem: BFS counts edges, but we need an algorithm that counts costs. The solution, discovered by Edsger Dijkstra in 1956, is elegant.

The key insight is simple: instead of processing cells in the order they were discovered (like BFS with its queue), we process cells in order of their total cost from the start.

Think of it this way. BFS uses a queue that says "first discovered, first processed." Dijkstra uses a priority queue that says "lowest cost so far, first processed." This single change transforms an algorithm that ignores costs into one that minimizes them.

We explore this algorithm in detail in the next chapter. For now, understand the motivation: when edges have different weights, we cannot just count steps. We must track the actual cost to reach each cell and always expand the cheapest option first.

Key Takeaways

• Real-world pathfinding involves varying costs for different edges or cells
• BFS finds the path with minimum steps, ignoring edge weights entirely
• A shorter path (fewer steps) can have a higher total cost than a longer path
• Costs can represent distance, time, effort, money, risk, or any other quantity we want to minimize
• We need algorithms that process cells by accumulated cost, not by order of discovery
• Dijkstra's algorithm, which we cover next, solves exactly this problem