The Algorithm Design Manual Second Edition

6

Weighted Graph Algorithms

191

6.1

Minimum Spanning Trees . . . . . . . . . . . . . . . . . . . . . .

192

6.2

War Story: Nothing but Nets . . . . . . . . . . . . . . . . . . . .

202

6.3

Shortest Paths . . . . . . . . . . . . . . . . . . . . . . . . . . . . .

205

6.4

War Story: Dialing for Documents . . . . . . . . . . . . . . . . .

212

6.5

Network Flows and Bipartite Matching

. . . . . . . . . . . . . .

217

6.6

Design Graphs, Not Algorithms . . . . . . . . . . . . . . . . . . .

222

6.7

Exercises . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .

225

---

C O N T E N T S