15. Weighted Graphs
In This Chapter
• Minimum Spanning Tree with Weighted Graphs
• The All-Pairs Shortest-Path Problem
In the preceding chapter you saw that a graph’s edges can have direction. This chapter explores 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 you 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 the shortest ...
Get Data Structures & Algorithms in Python 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.
