Dutor

Bellman-Ford算法简述

　　Dijkstra算法是处理单源最短路径的有效算法，但它局限于边的权值非负的情况，若图中出现权值为负的边，Dijkstra算法就会失效，求出的最短路径就可能是错的。这时候，就需要使用其他的算法来求解最短路径，Bellman-Ford算法就是其中最常用的一个。该算法由美国数学家理查德•贝尔曼（Richard Bellman, 动态规划的提出者）和小莱斯特•福特（Lester Ford）发明。Bellman-Ford算法的流程如下：
　　给定图G(V, E)（其中V、E分别为图G的顶点集与边集），源点s，

1. 数组Distant[i]记录从源点s到顶点i的路径长度，初始化数组Distant[n]为, Distant[s]为0；
2. 以下操作循环执行至多n-1次，n为顶点数：
   • 对于每一条边e(u, v)，如果Distant[u] + w(u, v) < Distant[v]，则另Distant[v] = Distant[u]+w(u, v)。w(u, v)为边e(u,v)的权值；
   • 若上述操作没有对Distant进行更新，说明最短路径已经查找完毕，或者部分点不可达，跳出循环。否则执行下次循环；
3. 为了检测图中是否存在负环路，即权值之和小于0的环路。对于每一条边e(u, v)，如果存在Distant[u] + w(u, v) < Distant[v]的边，则图中存在负环路，即是说改图无法求出单源最短路径。否则数组Distant[n]中记录的就是源点s到各顶点的最短路径长度。

　　可知，Bellman-Ford算法寻找单源最短路径的时间复杂度为O(V*E).

Dijkstra算法简述

　　Dijkstra算法是图论中的一种求单源最短路的算法，即从一个点开始到所有其他点的最短路。其基本原理是：集合T包含所有当前已经找到最短路径的点，初始情况下T中只有源点U = V – T，其中V为图G的点集。从源点开始，每次新扩展一个属于U、距离T中点最短的点，用该点更新U中的与其相邻的点的距离。当所有边权都为正时，由于不会存在一个距离更短的没扩展过的点，所以这个点的距离永远不会再被改变，因而保证了算法的正确性。不过根据这个原理，用Dijkstra求最短路的图不能有负权边，因为扩展到负权边的时候会产生更短的距离，有可能就破坏了已经更新的点距离不会改变的性质。若要处理含有负权值边的情况，就需要使用Bellman-Ford算法了。

Dijkstra算法流程

　　在以下说明中，start为源，Adj[u,v]为点u和v之间的边的长度，结果保存在Closest[]

• 初始化：源的距离Closest[start]设为0，其他的点距离设为无穷大，同时把所有的点的状态设为没有扩展过。
• 以下过程循环n-1次：
  在没有扩展过的点中取一距离最小的点u，并将其状态设为已扩展。
  对于每个与u相邻的点v，如果Closest[u]+Adj[u,v] < Closest[v]，那么把Closest[v]更新成更短的距离Closest[u]+Adj[u,v]。此时到点v的最短路径上，前一个节点即为u。
• 结束。此时对于任意的u，Closest[u]就是start到u的距离。

　　一个无向、加权、连通图的生成树是指这样一棵树，它包含该图所有的n个顶点，和该图边集E中的n-1个边。最小生成树就是该图所有生成树中各边权值之和（构造代价）最小的生成树。求指定图的最小生成树有多种算法，除了这里要介绍的Kruskal算法，还有Prim算法、Sollin算法等。

Kruskal算法描述

　　用Kruskal算法为无向加权连通图G构造最小生成树T的步骤如下：首先初始化T为一个包含所有n个顶点、0个边的森林，E为G的边集。每次从E中取出一条具有最小权值的边（并从E中删除该边），如果该边不与T中其他边构成回路，则将该边加入T，否则舍弃该边。重复上述操作至T中含有n-1条边，此时T即Kruskal算法构造出的最小生成树。

Kruskal算法证明

　　易证，对于一个无向加权连通图，总是存在一棵或以上的有限课生成树，而这些生成树中肯定存在至少一棵最小生成树。下面证明Kruskal算法构造的生成树是这些最小生成树中的一棵。
　　设T为Kruskal算法构造出的生成树，U是G的最小生成树。如果T==U那么证明结束。如果T != U，我们就需要证明T和U的构造代价相同。由于T != U，所以一定存在k > 0条边存在于T中，却不在U中。接下来，我们做k次变换，每次从T中取出一条不在U中的边放入U，然后删除U一条不在T中的边，最后使T和U的边集相同。每次变换中，把T中的一条边e加入U，同时删除U中的一条边f。e、f按如下规则选取：a). e是在T中却不在U中的边中最小的一条边；b). e加入U后，肯定构成唯一的一个环路，令f是这个环路中的一条边，但不在T中。f一定存在，因为T中没有环路。