这是找到最短路径的最佳算法(时间复杂度)

Question

我有一个邻接矩阵。我必须计算最短+备用路径：

1. 从一个顶点（A）到另一顶点（B）
2. 从所有顶点到单个顶点
3. 一对顶点的
4. 从每个顶点每隔一个顶点

我必须使用图形算法（dijkstra，BellManford，BFS）来计算所有这些。有人能建议我哪种算法是实现这些功能的最佳算法吗。

*最好意味着最少的时间；复杂性

Answer 1

这在很大程度上取决于您的数据。维基百科对可用的不同算法有一个很好的概述，以及一些关于这些算法何时有用的线索。一个重要因素是是否可以对边的权重进行一些限制。基本分类通常如下：

相同的正权重

如果所有权重都相同且为正，那么我们本质上希望使用最小数量的边来找到路径。在这种情况下，我们可以使用广度或深度优先搜索来找到O（E+V）时间内的单源最短路径。然后将其直接扩展到O（EV+V²）时间中的所有对。

非负边权重

对于单源最短路径问题，可以使用Dijkstra的算法。对于普通的二进制堆，这会使您的时间复杂度为O（（E+V）logV）。使用Fibonacci堆，可以将其改进为O（E+V log V），这对于密集图来说更快。

或者，还有Gabow的缩放算法，它的运行时间为O（E log_{RL）时间，其中R是E/V，L是边的最大长度，但该算法比Dijkstra的算法复杂得多。}

为了找到一对顶点之间的最短路径，您可以使用A*算法（或其衍生物之一），但这取决于合适的启发式算法的可用性。

负边权重，但没有负循环

采用Bellman-Ford算法求解单源最短路径，时间复杂度为O（VE）。

在O（EV+V²logV）时间内，所有对的最短路径都可以用Johnson算法求解。此外，还有Floyd-Warshall算法，它在O（V³）中求解：这在稠密图上通常更快。