最短路径算法

本章教程详细介绍了 4 个最短路径算法,分别是戴克斯特拉算法、贝尔曼-福特算法、弗洛伊德算法、和 A*算法。取决于问题的要求和图的特征,我们在不同的情况下选择用不同的最短路径算法。

当图中没有负权重,且问题只要求获得从一个节点到一个或多个节点的最短路径时,戴克斯特拉算法和 A*算法是我们的首选算法。但是当图中有负权重时,我们则要依赖贝尔曼-福特算法和弗洛伊德算法,其中两者的区别是弗洛伊德算法计算所有节点对之间的最短路线,而贝尔曼-福特算法只计算图中一个节点到其他节点的最短路线。
本章内容:
1. 戴克斯特拉算法
2. 贝尔曼-福特算法
3. 弗洛伊德算法
4. A*搜索算法