本文共 767 字，大约阅读时间需要 2 分钟。
在AGV导航中，路径选择是一个重要课题，如果最优路径使用最短路径算法，那可以使用的算法有很多，本文比较了当前流行的最短路径算法，主要有Dijkstra 算法，Floyd算法，A-star算法，Bellman-Ford 算法，SPFA算法等
下表是对各种算法的一个比较：
| 算法 | 适用场景 | 实现难易度 | 时间/空间复杂度 | 负权边问题 |
| Floyd算法 | 多源最短路径，计算任意两点之间的最短距离; 稠密图效果最佳; 时间复杂度比较高，不适合计算大量数据; | 简单 | 时间复杂度:O(n^3) 空间复杂度:O(n^2) | 可以处理 |
| Dijkstra 算法 | 单源最短路径，计算一个点到图中其他点之间的最短距离; 稠密图；
| 中等 | 时间复杂度: O((N+M)logN) 空间复杂度:O(M) | 不能处理 |
| A-star算法 | 单源最短路径，可以平衡效率和路线质量，找到次优路线的搜索算法； 是对 Dijkstra 算法的优化和改造； | 复杂 | 时间复杂度: O((N+M)logN) 空间复杂度:O(M) | 不能处理 |
| Bellman-Ford 算法 | 单源最短路径 稀疏图 | 中等 | 时间复杂度:O(MN) 空间复杂度:O(M) | 可以处理 |
| SPFA算法 | 单源最短路径 对Bellman-Ford 算法的优化 稀疏图 | 中等 | 时间复杂度最坏也是O(MN) 空间复杂度:O(M) | 可以处理 |
因为AGV导航需要计算任意两点的最短路径，所以我们需要一个多源最短路径算法。Floyd算法满足此需求，同时实现简单，易于理解，虽然时间复杂度高，但是如果应用场景中导航点的个数不是天文数字的话，还是可以承受的。
References:
A-star 算法原理分析:
Floyd算法：
Dijkstra（迪杰斯特拉算法）的实现：
最短路径问题：
Bellman-Ford算法：
SPFA 算法：
转载地址：https://blog.csdn.net/lclfans1983/article/details/105391433 如侵犯您的版权，请留言回复原文章的地址，我们会给您删除此文章，给您带来不便请您谅解！
发表评论
最新留言
关于作者
