最短路径分析的算法

分手后的思念是犯贱 2023-06-18 03:59 23阅读 0赞

#### Floyd-Warshall（弗洛伊德算法） ####

弗洛伊德算法的主要思想是通过第三点来缩短两点间的路径，例如顶点a和顶点b之间的路径为dis\[a\]\[b\]，如果想使a,b之间的路径缩短，只有引入第三点k，并通过k点来中转，即a->k->b，才可能缩短a,b之间的路径，那么这个k点是哪个点呢，其实并不唯一，k点也有可能有多个，但可以确定的是，在经过k点中转后，所得到的dis\[a\]\[k\]+dis\[k\]\[b\]一定小于中转前的dis\[a\]\[b\]，所以就可以总结为从a点到b点只经过前k个点的最短路径，是不是感觉这句话有点熟悉呢\[滑稽\]，没错，这就是动态规划的思想。

#### Dijkstra（迪杰斯特拉）算法 ####

迪杰斯特拉算法是解决单个点到其余各点最短路径的算法，其主要思想为通过其他边来松弛单个点到其余各点的路程。这里我们还需要定义一个dis数组，表示该点到其余各点的未确定最短距离。然后从dis数组中选取一个最小值（离始点最近的点），将它的距离确定为最短，这里是因为每条边都是正数，那么肯定不可能通过第三个点来使得此时距始点最短的距离更短了，因为始点到其他点的距离都比到这个点的距离要大。

然后我们就可以通过这个点的边来对始点到其他点的边进行“松弛”，比如设始点为1号点，刚刚确定为最短路径的点为2号点，然后此时的dis\[3\]=10,dis\[2\]=1,e\[2\]\[3\]=4(始点为2，终点为3的边)，这时我们就可以通过e\[2\]\[3\]这条边来对dis\[3\]进行松弛，因为dis\[3\]>dis\[2\]+e\[2\]\[3\]，所以此时的dis\[3\]应更新为5。

这便是迪杰斯特拉算法的主要思想：通过其他边来松弛单个点到其余各点的路程。

这样我们就可以总结出算法的基本步骤了：每次找到离始点最近的一个顶点，通过这个点的边来对始点到其余各点的边进行松弛，最终得到始点到其余各点的最短路径。

#### Bellman-Ford（贝尔曼-福特）算法——解决负权边 ####

在以上介绍的两种算法中虽然很好的解决了最短路径问题，但多多少少都有一些缺陷，比如无法解决带有负权回路的图。现在我们介绍的这种Bellman-Ford算法就能够解决负权边问题啦O(∩\_∩)O~

Bellman-Ford算法其实操作方法与Dijkstra算法如出一辙，只不过它没有进行最短路径的猜测，而是对每一条边都进行了n-1次松弛，这样就确保了每一条边最后都能到达它的最短路径。

#### SPFA（Bellman-Ford算法的队列优化） ####

在刚刚的算法中我们提到，对每一条边都进行n-1次的松弛，可能会进行很多不必要的操作，浪费掉很多时间，顺便说一下，不进行优化的Bellman-Ford算法的时间复杂度为O(n*m)，而经过队列优化的Bellman-Ford算法的时间复杂度最坏情况下也是O(n*m)，但是一般是达不到的。

那么我们应该如何利用队列进行优化呢？我们可以将始点u放入队列，然后对u的所有出边进行松弛。例如有一条u->v的边，如果通过u->v这条边使得始点到顶点v的路程变短（dis\[u\]+e\[u\]\[v\]<dis\[v\]），且顶点v不在队列中，就将点v放入队尾，点u松弛完毕后，就将点u出队，继续进行下一点的出边松弛，直到队列为空。