比 Dijikstra 更快的算法，用于查找从一个节点开始到所有节点的最短路径

Question

我正在寻找一种类似于 dijikstra 的算法，但速度更快。我必须解决同样的问题 - 从给定节点开始找到到所有节点的最短路径。但我的老师告诉我，我应该找到一种更快的算法，因为 dijikstra 可能会很慢。我还想问，我是否可以使用弗洛伊德马歇尔的算法来完成该任务

Answer 1

这里是这个问题的一个解决方案，如果所有的弧都是非负的，否则是贝尔曼-福特。 要获得所有最短路径：

1. 进行拓扑排序。
2. 从根开始广度优先搜索并更新距离。 完成。

仅从一个节点v开始，从v开始，而不是从你的根开始。在最坏的情况下，你的节点 v 无论如何都是根。所以时间复杂度仍然= O(|V|+|E|)。

Answer 2

Dijkstra 是找到从节点到其余节点的最短路径的最佳算法，如果它不是特定的图，则总是因为弧权重为正，否则您需要使用 Bellmann-Ford 算法。在你的情况下，它是一个 DAG，这是一个特殊的图，它没有循环，你永远不会回到以前的状态，因此，从任何节点到另一个节点（或没有）都有一条唯一的路径。因此，即使弧为负，BFS 或 DFS 等算法也是合适的。

Answer 3

请参考下表做出最佳选择。

算法	时间复杂度（大O）	空间复杂度（大O）	直接图还是非直接图？	处理循环图？	处理负边权重？	什么时候使用？
Dijkstra 算法	(E+V)LogV	V	两者	没有	没有	获取从单个源到所有顶点的最短路径
贝尔曼-福特算法	VE	V	两者	不适用于负体重周期	是的	获取从单个源到所有顶点的最短路径
拓扑排序算法	V+E	V	直接	没有	是的	获取从单个源到所有顶点的最短路径
Floyd-Warshall 算法	V^3	V^2	两者	不适用于负体重周期	是的	获取从所有顶点到所有顶点的最短路径