15. Weighted Graphs

In This Chapter

Minimum Spanning Tree with Weighted Graphs

The Shortest-Path Problem

The All-Pairs Shortest-Path Problem

Efficiency

Intractable Problems

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 live online training, plus books, videos, and digital content from nearly 200 publishers.