【读书笔记】算法漫步 第9章

问题11 最短路径

 

图的最短路径问题是一个图的基本问题。最短路径问题的应用很广。

 

图的最短路径问题不是一个问题，而是一个问题集合。本书在介绍算法时，没有明确给出具体的问题描述，读者要注意，不要混淆了。

 

本章在介绍问题求解时，按照算法基本思想—算法描述—算法运行示例—算法分析这4个步骤展开介绍。【作者感受，这个4个步骤是学习各种算法的标准步骤，对学习者各方面能力的训练都有帮助，还可以加上，代码实现，就更完整】

 

本章首先介绍了一个基于广度优先搜索（BFS）算法求解算法【建议先了解DFS和BFS】。

然后介绍了在数据结构、算法教材中最常见的经典算法Dijkstra算法（这是图灵奖获得者Dijkstra发明的算法）。这里就不详细介绍了，推荐自读。

 

【作者感受】

求解图的最短路径问题的有效算法值得学习，因为图的最短路径应用非常广泛。

图的最短路径有很多（图的）特色性质，有兴趣的读者可以在图论中学习。

针对图的最短路径问题，可以采用很多种算法设计策略（如贪心、动态规划等）。不同的算法可能展现出不同的优势，更好地适应不同的输入数据（图）；同时，学习不同的算法，分析不同算法的性能（效率和适用性），可以加深对最短路径问题的理解，训练读者的算法思维。

要高效实现最短路径算法的实际运行时间，需要一些复杂的数据结构的支持（空间换时间）。

证明最短路径算法的正确性，需要用到图论的一些知识，还会用到归纳法或反证法，需要一定的数学基础。

 

学习本章，对算法逻辑、程序和数据结构、数学知识都涉猎，有一点难度，但是难度还好。

所以，最短路径算法是数据结构、算法教材中必有的内容。

 

而且，最短路径问题中，直至目前为止，求解单点到单点的最短路径在理论上没有发现比求解单点到其他各点最短路径更优的算法。然而，在大规模图中，如何针对特定的问题或需求，设计出实际有效（运行时间满足应用需求）的求解最短路径程序也是蛮有意义的。