最短路径算法

Dijkstra算法 link

Dijkstra算法用于计算加权图中一个顶点到其他顶点的最短距离。

Dijkstra算法不支持权值包含负值的加权图，因为算法每次都是取距离最小的顶点更新其邻接顶点的，若邻接顶点存在一个负数边，当前顶点$v$到邻接顶点$u$的距离会比当前顶点的距离更小，导致下一迭代会从$u$开始又更新$v$的距离为一个更小的距离，算法陷入死循环。

若所有边同时加上一个固定数值结果将不再正确，因为在所有到其他顶点的最短路径中，所包含的边数量并不一定一致。

Dijkstra算法实现 link

Dijkstra算法的核心思想是初始化一个源顶点到其他顶点的距离映射表(源顶点到源顶点的距离为0，到其他节点为无穷大)，每次从集合中取出距离源顶点最小的顶点$v$，若由v到其邻接顶点的距离更短则更新邻接顶点的在集合中的距离值，直到所有顶点从集合中取出来。我们可以通过最小堆快速取出距离最小的顶点，通过哈希映射来维护顶点的距离值。值得注意的是，使用编程语言提供的最小堆一般不支持动态调整堆中元素的大小，我们只需重复插入距离更短的顶点即可，并不会影响我们取出的最小值。

• 时间复杂度：$O(E*\log V)$，在$O(1)$复杂度内建立最小堆Heap，堆中至多$O(E)$个顶点，至多进行$O(E)$次pop()操作和$O(E)$次push()操作，而pop()和push()的时间复杂度均为为$O(\log E)=O(\log V^2)=O(\log V)$。HashMap在良好的哈希函数下能做到$O(1)$复杂度的插入和更新操作。
• 空间复杂度：$O(V)$，我们使用了一个Heap和一个HashMap额外存储顶点信息。

Floyd Warshall算法 link

Floyd Warshall算法用于计算加权图所有顶点间的最短距离。Floyd Warshall算法可以计算是包含负值的加权图，但不支持闭环为权重之和为负数的加权图。

Floyd Warshall算法实现 link

• 时间复杂度：$O(V^3)$，算法中包含三个相互嵌套的循环。
• 空间复杂度：$O(V)$, 我们使用了一个HashTable存储各顶点间的距离。

Bellman Ford算法 link

前面讨论的Dijkstra算法有一个限制条件是图中不能包含权重为负数的边，因为再次访问已访问的顶点，否则将导致死循环。Bellman Ford算法不是从最短距离节点开始更新邻接顶点的最短路径，而是通过遍历所有边并更新从边对端的最短路径，他可以解决Dijkstra算法不能计算包含权重为负数的边的问题。图中不能包含权重之和为负数的闭环，因为围绕环绕一圈，距离就会变小，最短路径不存在。

迭代多少次可以确定所有顶点的最短距离？通过观察可以发现，每次迭代可以确定至少一个顶点的最短距离，而且从源点到其他任意顶点的最短路径的边数一定小于等于$V-1$，因为大于$V-1$将导致闭环，故迭代$V-1$次可以确保所有顶点获取到最短路径。正常来讲，若图中权重之和为负数的闭环则第$V$次迭代则不会有顶点最短距离更新，若第$V$次迭代仍有顶点最短距离更新，图中存在权重之和为负数的闭环。

Bellman Ford算法实现 link

Bellman Ford算法的核心思想是经历$V-1$迭代，每次迭代遍历次所有边，期间利用从一端到对端的距离更新对端的距离，从而确保所有顶点的距离被更新到正确的值。第$V$次迭代若发生节点位置变更，说明图中形成了负权重环。

• 时间复杂度：$O(VE)$，我们进行了$O(V)$次时间复杂度为$O(E)$的边遍历。
• 空间复杂度：$O(V+E)$, 我们使用了两个数组用于存储顶点和边进行遍历。

Johnson算法 link

Floyd Warshall算法计算所有顶点间最短距离的时间复杂度为$O(V^3)$，采用Dijkstra算法对每个顶点求解最短距离的复杂度会更小，但Dijkstra算法有一个限制条件是图中不能包含权重为负数的边。Johnson算法可以破除这个限制，它的思路是将图中所有的负权值边转换为正权值边。

为了确保最终的最短路径不变，就需要保证每条从源点到终点的不同路径的权值都增加或减少相同的数值，由于路径中所包含的边不尽相同，对所有边加相同权重不是一个好的思路。Johnson算法是在路径沿线节点添加权值$h[v]$，通过$w‘(u,v)=w(u,v)+h[u]-h[v]$计算边的权值，这样的好处是每条路径沿线的计算会相互抵消，最终都会增加一个相同的值。

怎么计算顶点权值数组$h$呢，这个数组需要确保$w‘(u,v)=w(u,v)+h[u]-h[v] >= 0$，即$h[v] <= h[u] + w(u, v)$。这个公式的意思是$h(v)$的值一定小于或等于经由中转顶点$u$到达的值，等价于$h$数组看作一个额外的与其他顶点直连的顶点$s$到其他任意顶点$v$的最短距离，直连所有顶点的目的是确保顶点$v$任意入方向的边都被考虑，这个距离能够满足上面的不等式。因为图中仍包含权重为负数的边，Johnson算法使用的是Bellman Ford算法计算$h$的值。

Johnson算法实现 link

• 时间复杂度：$O(VE\log V + VE)$，一次bellman_ford算法的时间复杂度为$O(VE)$，$O(V)$次Dijkstra算法的时间复杂度为$O(VE\log V)$
• 空间复杂度：$O(E+V)$, 我们使用了一个HashMap和一个Graph分别存储计算出来的顶点权重以及修改后边权重之后的图。