简介

图的单源最短路径问题的算法，速度较慢但可适用于所有图，事件复杂度 O(n*m)

基本理论模型

松弛操作

所谓松弛操作是指如下代码

private relax(int v,int u){ if(dist[v] + edge[v][u] < dist[u]){ dist[u] = dist[v] + edge[v][u]; } }

其中， dist 表示从源点到指定节点的最短路径，那么如何理解这段操作呢？

如上图所示，如果借助 v 到达 u 的距离比原先认为的最短距离要短，那自然可以借助 v 到达 u 从而更新最短距离

算法流程

初始 dist 数组，到源点的距离为 0 ，其他皆为无穷遍历所有边并执行松弛操作循环第二步 n - 1 次， n 是节点的个数

除此看见这个过程你可能感到非常不解，不妨先看看一个例子

以 1 为源点，初始化 dist 数组为

1234560$\infty$$\infty$$\infty$$\infty$$\infty$

不妨手动的尝试一次对全体边集的松弛操作，此时将获得新的 dist 数组

1234560111$2or\infty$$2or\infty$

你可能注意到了， 5 和 6 号节点的 dist 值是不定的，事实上这取决于你访问边的顺序，当我们访问 edge[2][5] 时，无法确定 dist[2] 是 1 还是无穷，因为我们可能还没有访问 edge[1][2]

但我们可以确定的是，第一轮结束后，2,3,4 的值必然是确定的，然后让我们再次看看第二轮的结果

123456011122

此时我们获得了最终的结果，可以看到哪怕我们没有进行 n - 1 次的遍历也获得了最终的结果

经过上述过程，可以观察到一个结果，经过 k 次边集的遍历，至少可以求出源点经过 1 到 k条边到达任意点的最短距离

怎么理解这句话呢？观察第一次遍历后的结果，对于 2,3,4 节点而言，我们求出了它经过 1 条边的最短距离为 1 ；而对于 5,6 节点而言，如果我们求出了 $\infty$ 则我们求出的是经过了 1 条边到达的结果，显然是不可达的，而如果求出了 $2$，则是提前求出了经过两条边可以到达的路径长度，这也正是“至少”的含义

而到了第二次遍历后，我们一定能求出 5,6 的值为 2，因为我们一定会求出它在经过 1 或 2 条边到达的最小距离

就此，我们正式明白了遍历一次边集的含义，因而为何要遍历 n - 1 次就不言而喻了。在没有负边及负环的情况下，源点到某点的最短路径至多包含 n 个节点，n-1条边

基本代码模板

public static long[] bellmanFord(int n, int[][] edges, int source) { // 初始化 long[] dist = new long[n]; Arrays.fill(dist, Integer.MAX_VALUE); dist[source] = 0; // 主体部分 for (int i = 0; i < n - 1; i++) { for (int[] edge : edges) { relax(edge, dist); } } return dist; } /** * 松弛 */ private static void relax(int[] edge, long[] dist) { if (dist[edge[0]] + edge[2] < dist[edge[1]]) { dist[edge[1]] = dist[edge[0]] + edge[2]; } }

时间复杂度 O(nm) n 为点数，m为边数

含负边模型

前面的算法本质上求的是在经过有限边数内到达任意点的最小距离，在没有负边的前提下，这就是全局的最小距离，而在有负边的情况下，则有可能产生无穷小最小距离的情况

观察上图，未标识的边皆为权重1，我们不难发现，对于 4,5 两个节点来说，他们只需要反复的游走于红色的环路，就可以不断的使得 dist 减少，这种环路就是所谓的 负环

所有负环内的节点都必然有 dist 值为负无穷，且这些节点所能够到达的节点也是如此

因此要兼容存在负环的图，我们就需要找到上述节点，并将其dist值定义为负无穷

方法也不难，再次不断的遍历边并松弛，对每一个出现 dist 值再次减少的节点标记其 dist 值为 负无穷，直到在一次遍历中没有找到可以再次减少 dist 值的节点，则说明所有节点都得到应有的值了

负权算法模板

public static long[] bellmanFord(int n, int[][] edges, int source) { // 初始化 long[] dist = new long[n]; Arrays.fill(dist, Integer.MAX_VALUE); dist[source] = 0; // 主体部分 for (int i = 0; i < n - 1; i++) { for (int[] edge : edges) { relax(edge, dist); } } boolean flag = true; while (flag) { flag = false; for (int[] edge : edges) { // 如果此时还能导致出现更小路径的情况，说明必有负环，更新负权边终点最短路径为负无穷 if (dist[edge[0]] + edge[2] < dist[edge[1]] && dist[edge[1]] != Integer.MIN_VALUE) { dist[edge[1]] = Integer.MIN_VALUE; flag = true; } } } return dist; } /** * 松弛 */ private static void relax(int[] edge, long[] dist) { if (dist[edge[0]] + edge[2] < dist[edge[1]]) { dist[edge[1]] = dist[edge[0]] + edge[2]; } }

优化

提前退出优化

前面提到，算法有可能“超前完成任务”，因此不妨简单的测试算法是否超前的完成了任务，从而提前的退出

// 主体部分 for (int i = 0; i < n - 1; i++) { boolean flag = false; // 检测此轮遍历有没有最短距离的变化 for (int[] edge : edges) { flag = relax(edge, dist); } if (!flag) { return dist;// 如果没有变化则说明已经可以返回了 } }

SPFA

纵观整个算法过程，不难看出，其时间消耗中有大量时间浪费在了无意义的对边的检视，例如最开始的例子

在第一次遍历时，我们之所以有可能获得 4,5 节点无穷的结果，就是因为我们率先遍历了 edge[2][5] 等边，而事实上这条边的检视只有在遍历 edge[1][2] 之后才有意义，却因为我们先遍历了 edge[2][5] 而不得不第二次遍历边集，因此第一次遍历 1edge[2][5]1 是无意义的，换句话说，对边的遍历应当具有某种时序性，而由此诞生而来的，正是 SPFA 算法