图论算法

图论算法

1、Relaxation(松弛操作)：

procedure relax(u,v,w:integer);//多数情况下不需要单独写成procedure。

begin

if dis[u]+w<dis[v] then

begin

dis[v]:=dis[u]+w;

pre[v]:=u;

end

end;

2、Dijkstra

适用条件&范围：

a) 单源最短路径(从源点s到其它所有顶点v);

b) 有向图&无向图(无向图可以看作(u,v),(v,u)同属于边集E的有向图)

c) 所有边权非负(任取(i,j)∈E都有Wij≥0);

1)算法描述：

a) 初始化：dis[v]=maxint(v∈V,v≠s); dis[s]=0; pre[s]=s; S={s};

b) For i:=1 to n

1.取V-S中的一顶点u使得dis[u]=min{dis[v]|v∈V-S}

2.S=S+{u}

3.For V-S中每个顶点v do Relax(u,v,Wu,v)

c) 算法结束：dis[i]为s到i的最短距离；pre[i]为i的前驱节点

2)算法优化：

使用二叉堆(Binary Heap)来实现每步的DeleteMin(ExtractMin，即算法步骤b中第1步)操作，算法复杂度从O(V^2)降到O((V+E)㏒V)。推荐对稀疏图使用。

使用Fibonacci Heap(或其他Decrease操作O(1),DeleteMin操作O(logn)的数据结构)可以将复杂度降到O(E+V㏒V)；如果边权值均为不大于C的正整数，则使用Radix Heap可以达到O(E+V㏒C)。但因为它们编程复杂度太高，不推荐在信息学竞赛中使用。

3、Bellman-Ford

1) 适用条件&范围：

a) 单源最短路径(从源点s到其它所有顶点v);

b) 有向图&无向图(无向图可以看作(u,v),(v,u)同属于边集E的有向图);

c) 边权可正可负(如有负权回路输出错误提示);

d) 差分约束系统;

2)算法描述：

对每条边进行|V|次Relax操作;

完成后，如果存在(u,v)∈E使得dis[u]+w<dis[v],则存在负权回路;否则dis[v]即为s到v的最短距离,pre[v]为前驱。

3)算法实现：

For i:=1 to |V| do

For 每条边(u,v)∈E do

Relax(u,v,w);

For每条边(u,v)∈E do

If dis[u]+w<dis[v] Then Exit(False)