最佳最短路径算法

Question

我正在努力思考各种最短路径算法，并确定每种算法何时合适。为此，我画了一个决策树，我的决定是：

1. 我想要来自单一来源的最短路径还是所有最短路径对？
2. 我的图表是循环的还是非循环的？
3. 我的图表是未加权的、严格正权重加权的，还是用正负权重加权的？

而我考虑的算法仅限于：BFS、Dijkstra（带二叉堆）、Bellman-Ford、Floyd-Warshall。

注1. 对于单源无环图我写了BFS/Linear。我的意思是节点在拓扑排序中的线性游走，如图here.

注 2. 对于全对未加权算法，我编写了 BFS（所有节点）/Floyd-Warshall。我写这篇文章是因为据我所知，这两种算法都没有明显优于另一种算法。在稀疏图上，我认为 BFS 更快，而在密集图上，我认为 Floyd-Warshall 更快。应用于每个节点的 BFS 是

O(V^2 + VE)

，对于稀疏图可以倾向于

O(V^2 + V)

，对于稠密图可以倾向于

O(V^2 + V^3)

。 Floyd-Warshall 总是

O(V^3)

.

注 3. 对于所有对正加权算法，我写了 Dijkstra（所有节点）/Floyd-Warshall。我写这篇文章是因为据我所知，这两种算法都没有明显优于另一种算法。在稀疏图上，我认为 Dijkstra 更快，而在密集图上，我认为 Floyd-Warshall 更快。应用于每个节点的 Dijkstra 是

O((V^2+VE) log V)

，对于稀疏图可以倾向于

O((V^2 + V) log V)

，对于密集图可以倾向于

O((V^2 + V^3) log V)

。