扬州网站建设哪个好薇网站策划书怎么写
有多种最短路径的应用场景，它们需要用到不同的算法来解决。除了贪心最优搜索之外，其他都是最优性算法，即得到的解都是最短路径。其中m是边的数量，n是点的数量。
| 问题 | 边权 | 算法 | 时间复杂度 |
|---|---|---|---|
| 一个起点，一个终点 | 非负数；无边权（或边权为1） | A*算法 | <O((m+n)logn) |
| 双向搜索 | <O((m+n)logn) | ||
| 贪心最优搜索 | <O(m+n) | ||
| 一个起点到其他所有点 | 无边权（或边权为1） | BFS | O(m+n) |
| 非负数 | Dijkstra（堆优化） | O((m+n)logn) | |
| 允许有负数 | SPFA | <O(mn) | |
| 所有点对之间 | 允许有负数 | Floyd | O(n^3) |
应该在不同的场景下有选择地使用。
（1）图的规模小，并且要求多源最短路，那么使用Floyd，如果边权有负数，则需要判断负环。
（2）图的规模大，且边的权值非负，用Dijkstra，SPFA虽然在Bellman-Ford算法上进行了很大的优化，但是最坏情况下依然是O(mn)，不稳定（比赛时，有的题目可能故意利用SPFA的不稳定性，如果一道题目的图规模很大，并且边的权值为非负数，它可能会故意设置不利于SPFA的测试数据，此时使用SPFA将会超时，要使用更稳定的Dijkstra）。
（3）图的规模很大，且边的权值有负数，用SPFA，并且需要判断负环。