4.4 最短路径
Robert Sedgewick Kevin Wayne
也许最直观的图处理问题就是你常常需要使用某种地图软件或者导航系统来获取从一个地方到达另一个地方的路径。我们立即可以得到与之对应的图模型：顶点对应交叉路口，边对应公路，边的权重对应经过该路段的成本，可以是时间或者距离。如果有单行线，那就意味着还需要考虑加权有向图。在这个模型中，问题很容易就可以被归纳为：
找到从一个顶点到达另一个顶点的成本最小的路径。
除了这类问题的直接应用，最短路径模型还适用于一系列其他问题（请见表 4.4.1），其中有一些看起来似乎和图的处理毫无关系。举个例子，我们会在本节的最后考虑金融学领域的套汇问题。
表 4.4.1 最短路径的典型应用
我们采用了一个一般性的模型，即加权有向图（它是 4.2 节和 4.3 节的模型的结合）。在 4.2 节中我们希望知道从一个顶点是否可以到达另一个顶点。在本节中，我们会把权重考虑进来，就像在 4.3 节中研究的加权无向图那样。在加权有向图中，每条有向路径都有一个与之关联的路径权重，它是路径中的所有边的权重之和。这种重要的度量方式使得我们能够将这个问题归纳为“找到从一个顶点到达另一个顶点的权重最小的有向路径”，也就是本节的主题。图 4.4.1 就是一个示例。
公开
同步至部落
取消
完成
0/2000
荧光笔
直线
曲线笔记
复制
AI
- 深入了解
- 翻译
- 解释
- 总结
本文深入介绍了图处理中的一个重要问题——最短路径，并介绍了最短路径问题的基本定义、相关算法（如Dijkstra算法和Bellman-Ford算法）、以及最短路径的性质。此外，还介绍了最短路径树的概念和加权有向图的数据结构。文章还介绍了加权有向图的API设计和测试用例，展示了最短路径的API和其在实际应用中的测试。通过这些内容，读者可以了解如何使用最短路径算法来解决实际问题，并可以通过测试用例验证算法的正确性和有效性。同时，文章还介绍了最长路径问题和并行任务调度问题，并提出了解决这些问题的算法。通过对无环加权有向图中的最长路径问题的讨论，读者可以了解到最长路径问题与最短路径问题的等价性，以及如何应用关键路径方法解决并行任务调度问题。整体而言，本文通过深入讨论最短路径问题及其相关算法和性质，为读者提供了全面的技术指导和实际应用示例，帮助他们更好地理解和应用最短路径算法。同时，通过介绍最长路径问题和并行任务调度问题，读者也可以了解到这些算法在其他领域的应用，为他们拓展思路和解决实际问题提供了重要参考。
仅可试看部分内容，如需阅读全部内容，请付费购买文章所属专栏
《算法（第 4 版）》
《算法（第 4 版）》
立即购买
登录 后留言
精选留言
由作者筛选后的优质留言将会公开显示，欢迎踊跃留言。
收起评论