Graphs 0/61

Dijkstra and shortest paths · 1 of 4

Shortest paths in weighted graphs

Define the length of a path and the distance in a weighted graph, see what BFS can and cannot do with weights, and find distances by relaxing every edge in rounds.

2,415 words · 11 min read

Part 1 of 5 Weighted graphs

Graphs with weights on the edges

Breadth-first search counts every edge the same, and the shortest path it finds is the one with the fewest edges. A road map is different. One road takes 1 minute and another takes 10, and the route we want is the one that takes the least time, however many roads it uses. A graph in which every edge carries a number is called a weighted graph, and the number is the weight of the edge. A weight can stand for minutes, for a length in kilometres or for the price of a ticket.

The courier map

Our example for the whole lesson is the map of a courier. It has five towns, numbered 0 to 4, and five one-way roads. The number on a road is the time it takes in minutes:

4121501234

The length of a path in a weighted graph is the sum of the weights of its edges. On the map, the path 0 → 1 → 3 has length 4+1=54 + 1 = 5, and the path 0 → 2 → 1 → 3 has length 1+2+1=41 + 2 + 1 = 4, although it uses one more road. As before, the distance from one vertex to another is the length of the shortest path between them, so the distance from town 0 to town 3 is 4. No road leads into town 4, so no path reaches it, and we say that its distance is infinite, written ∞\infty.

The problem of this lesson is to find the distance from one starting vertex, called the source, to every other vertex. For the courier map with town 0 as the source, the answer is:

The number under each cell is the town.

A weighted graph is stored in adjacency lists like any other graph, with one change: each entry is a pair, made of the neighbor and the weight of the edge that leads to it. These are the lists of the courier map:

graph[0]  (1, 4)  (2, 1)graph[1]  (3, 1)graph[2]  (1, 2)  (3, 5)graph[3]graph[4]

The pair (1, 2) in the list of town 2 is the road from town 2 to town 1, which takes 2 minutes.