The Algorithm Design Manual Second Edition

6.3

Shortest Paths

A path is a sequence of edges connecting two vertices. Since movie director Mel

Brooks (“The Producers”) is my father’s sister’s husband’s cousin, there is a path

in the friendship graph between me and him, shown in Figure

6.7

—even though

the two of us have never met. But if I were trying to impress how tight I am with

Cousin Mel, I would be much better off saying that my Uncle Lenny grew up with

him. I have a friendship path of length 2 to Cousin Mel through Uncle Lenny, while

---

206

6 .

W E I G H T E D G R A P H A L G O R I T H M S

Steve                  Dad              Aunt Eve        Uncle Lenny       Cousin Mel

Figure 6.7: Mel Brooks is my father’s sister’s husband’s cousin

s

t

Figure 6.8: The shortest path from s to t may pass through many intermediate vertices

the path is of length 4 by blood and marriage. This multiplicity of paths hints at

why finding the shortest path between two nodes is important and instructive, even

in nontransportation applications.

The shortest path from s to t in an unweighted graph can be constructed using a

breadth-first search from s. The minimum-link path is recorded in the breadth-first

search tree, and it provides the shortest path when all edges have equal weight.

However, BFS does not suffice to find shortest paths in weighted graphs. The

shortest weighted path might use a large number of edges, just as the shortest route

(timewise) from home to office may involve complicated shortcuts using backroads,

as shown in Figure

6.8

.

In this section, we will present two distinct algorithms for finding the shortest

paths in weighted graphs.