4.5.4 图的最短路径
给定一个图中的两个顶点，一条路径是通过边连接的一系列顶点。最短路径是这些路径中边的数量最少的一条路径（可能存在多条最短路径）。图中最短路径示意图如图4-5-8所示。
图4-5-8 图中最短路径示意图
查找图中连接两个顶点的最短路径是计算机科学的一个基本问题。最短路径已被很好和成功地应用于解决各种各样的大规模问题，从互联网路由到金融套汇交易到研究大脑中神经元的动态。
作为一个例子，假设你是一个假想的廉价航空公司的一位顾客，该航空公司只在有限的城市间提供有限数量的航线。假设从一个地方到另一个地方的最佳方法是把航班数量减少到最低，因为从一个航班转机到另一个航班的延误可能是漫长的（也许最好的办法是考虑支付更多的钱使用另一家航空公司的直飞航线！）。一个最短路径的算法正是你规划旅行时需要的工具。这样的应用程序符合基本问题的理解和解决问题的方法的直觉。在这个例子的背景下讨论这些主题后，我们将考虑一个图模型更加抽象的应用程序。
根据应用程序的不同，客户端对于最短路径的要求也不相同。是否需要连接两个给定顶点的最短路径？或仅仅需要最短路径的长度？是否存在大量类似的查询？是否存在一个特别感兴趣的顶点？我们的选择是基于表4-5-4所示的API开始我们的讨论。
表4-5-4 PathFinder数据类型的API
在超大图中或对于大量的查询，我们需要特别注意API的设计，因为图计算的代价也许会令人望而却步。使用上述设计方案，客户端可以为给定图和给定顶点创建一个PathFinder对象，然后使用该对象查找到图中任何其他顶点最短路径的长度，或者遍历最短路径上的顶点。这些方法的一种实现被称为单源最短路径算法（single-source ...
Get 程序设计导论：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.
