14. Weighted Graphs
In This Chapter
In the preceding chapter we saw that a graph’s edges can have direction. In this chapter we’ll explore another edge feature: weight. For example, if vertices in a weighted graph represent cities, the weight of the edges might represent distances between the cities, or costs to fly between them, or the number of automobile trips made annually between them (a figure of interest to highway engineers).
When we include weight as a feature of a graph’s edges, some interesting and complex questions arise. What is the minimum spanning tree for a weighted graph? What is ...