14. Weighted Graphs

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 ...

Get Data Structures and Algorithms in Java, 2nd Edition now with the O’Reilly learning platform.

O’Reilly members experience books, live events, courses curated by job role, and more from O’Reilly and nearly 200 top publishers.