1 求含有负权边的图的单源最短路径——Bellman Ford算法与SPFA算法综合分析(上).docVIP

求含有负权边的图的单源最短路径——Bellman Ford算法与SPFA算法综合分析 对于不含负权边的图求单源最短路径，Dijkstra算法是最高效的。但是在含负权边的图中，Dijkstra很可能得不到正确的结果，因为Dijkstra每次选的是当前能连到的边中权值最小的，在正权图中这种贪心是对的，但是在负权图中就不是这样了。比如1——2权值为5，1——3权值为6，3——2权值为-2，求1到2的最短路径时，Dijkstra就会选择权为5的1——2，但实际上1——3——2才是最优的结果。 ???? Bellman-Ford与SPFA都是解决这一问题的算法，两者的程序都很简单清晰【其实后者就是前者的一个优化】，所以也比较容易掌握 一、Bellman-Ford算法 ????? 说到Bellman-Ford一定会说到松弛（relaxation）技术，即用d[i]来预计s到i的最短距离。在计算过程中不断地缩小d[i]，直到最后d[i]就是源点s到i的最短距离。至于为什么叫“松弛”，尽管算法导论中给出了一段说明，但我们只需认为这是作者在故弄玄虚即可，松弛就是求单源最短路径的迭代过程，d[i]也可以看为存储当前s到i的最短距离。 ??????? 算法核心代码如下：（针对有向图，Pascal语言） ??? 阅读上述程序，求解下图各点到点1的最短距离： 各点距离：0 2 5 9 11 14 棕色部分： n为图顶点数，m为图边数。 Cost[i,j]表示边（i，j）的权 Edge存放图的所有边 D即上文所述的用于存储当前s到i的最短距离的数组 Closest[i]记录s到i的最短路径上i的前趋。最后要求i到s的路径时，只需用递归打印Closest[i]、Closest[Closest[i]]、Closest[Closest[Closest[i]]、…、s便可求出整条路径。 绿色部分： 算法的初始化。 对于不为s的所有i∈V，d[i]初始赋为一个足够大的数来表示无限大【之所以不使用maxlongint而是使用100000000是因为下面要有无限大与实数相加的操作，如果maxlongint就会溢出（201错误）】，closest[i]赋为-1表示nil。d[s]赋为0表示s到s的距离为0。 红色部分： 算法的迭代求解部分。 程序很好理解，就是不断枚举每条边，更新当前找到的最短路径。对于不含负权回路的图，循环n-1次一定能对任意i使d[i]为s到i的最短路径，因为这段过程相当于枚举了s到其他所有点的所有路径。I—s，最短路最多含n-1条边，更新n-1次也就全部更新完毕。 蓝色部分： 算法的检验部分。 上面已经提到，如果是不含负权回路的图，d[i]一定是最短路径，不存在还需要更新的可能性，所以不会执行到exit(false)；至于当exit(false)时一定是存在负权回路的原因，算法导论上有一个比较复杂的证明，但是抛弃严谨的证明的话，理解起来却很容易：当图不含负权回路时一定不会exit(false)，逆否命题为当exit（false）时一定含负权回路。原命题成立，因此逆否命题一定成立。???????? 从流程可以看出，Bellman-Ford的时间复杂度为O(EV)，对于E接近V^2的稠密图为O(V^3)，对于E接近V的稀疏图为O（V^2）。??????? 当然，我们可以看到Bellman-Ford做了很多不必要的判断。如果i还没有循环到n-1但已经计算出最小路径时，d边不会再更新，但是循环却还要做到n-1，接下去的运算全部都是没有用的运算。所以我们在循环中加一个布尔型变量flag，进入外循环时flag设为false，若d有变化则flag改为true。在内循环全部做完后若flag还是false则说明算法已经完毕，直接退出算法并返回true。改进后的算法如下：???? 紫色部分为加入的语句。 这样虽然时间复杂度仍为O（VE），但是效率显然会有所提高。 1 2 3 4 5 6 2 3 7 4 15 2 3 7 25