图论的基本算法

1)      适用条件&范围：

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

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

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

2)      算法描述：

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,W_u,v)

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

3)      算法优化：

    使用二叉堆(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)。但因为它们编程复杂度太高，不推荐在信息学竞赛中使用。

注：程序使用二叉堆

程序：

program mtx_grp;
const num=10; max=10000;
type
 grp=array[1..num,1..num] of integer;
 rcd=set of 1..num;
 arr=array[1..num] of integer;
 arr2=array[1..num] of rcd;
var
i,j,w,m,n,e,k:integer;
g:grp;
visited:array[1..num] of boolean;
path:arr2;
dist,s:arr;

procedure createmtx;
 var i,j,k:integer;
 begin
  for i:=1 to n do
    for j:=1 to n do
      g[i,j]:=max;

  for k:=1 to e do
    begin
      readln(i,j,w);
      g[i,j]:=w;
      g[j,i]:=w;
    end;
 end;
procedure print( g:grp);
  begin
    for i:=1 to n do
      begin
        for j:=1 to n do
          if g[i,j]=max then write('oo':4)
             else write(g[i,j]:4);
        writeln;
      end;
  end;
procedure dijkstra(var dist:arr;var path:arr2;i:integer);
  begin
    e:=i;
    for j:=1 to n do begin
      if j<>i then s[j]:=0 else s[j]:=1;
      dist[j]:=g[i,j];
      if dist[j]<max
         then path[j]:=[i]+[j]
         else path[j]:=[];
    end;
    for k:=1 to n-2 do
      begin
        w:=max;m:=i;
        for j:=1 to n do
          if (s[j]=0) and (dist[j]<w) then begin m:=j;w:=dist[j];end;
        if m<>i then s[m]:=1 else exit;
        for j:=1 to n do
          if (s[j]=0) and (dist[m]+g[m,j]<dist[j])
            then begin
                   dist[j]:=dist[m]+g[m,j];
                   path[j]:=path[m]+[j];
                 end;
      end;
      for i:=1 to n do
       if i<>e then begin
          for j:=1 to n do
            if j in path[i] then write(j:3);
          writeln('w=':4,dist[i]);
       end;
  end;

begin
  assign(input,'nodelst5.in');
  reset(input);
  readln(n,e);
  createmtx;
  writeln;
  readln(i);
  dijkstra(dist,path,i);
  writeln;
end.

2.Floyd-Warshall

1)        适用范围：

a)       APSP(All Pairs Shortest Paths)

b)       稠密图效果最佳

c)       边权可正可负

2)        算法描述：

a)       初始化：dis[u,v]=w[u,v]

b)       For k:=1 to n

For i:=1 to n

    For j:=1 to n

        If dis[i,j]>dis[i,k]+dis[k,j] Then

            Dis[I,j]:=dis[I,k]+dis[k,j];

c)       算法结束：dis即为所有点对的最短路径矩阵

3)      算法小结：

此算法简单有效，由于三重循环结构紧凑，对于稠密图，效率要高于执行|V|次Dijkstra算法。时间复杂度O(n^3)。

考虑下列变形：如(I,j)∈E则dis[I,j]初始为1,else初始为0，这样的Floyd算法最后的最短路径矩阵即成为一个判断I,j是否有通路的矩阵。更简单的，我们可以把dis设成boolean类型，则每次可以用“dis[I,j]:=dis[I,j]or(dis[I,k]and dis[k,j])”来代替算法描述中的蓝色部分，可以更直观地得到I,j的连通情况。

与Dijkstra算法类似地，算法中蓝色的部分可以加上对Pre数组的更新，不再赘述。

4)        程序（直接写上的。或许有小错误）

program floyd

var i,j,k,n,m:longint;

leng:array[0..1001,0..1001]of longint;

begin

readln(n);

for i:=1 to n do

begin for j:=1 to n do

read(a[i,j]);

readln;

end;

end.

3.Prim

1)        适用范围：

a)       MST(Minimum Spanning Tree,最小生成树)

b)       无向图(有向图的是最小树形图)

c)       多用于稠密图

2)        算法描述：

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

b)       For i:=1 to n

1.取顶点v∈V-S使得W(u,v)=min{W(u,v)|u∈S,v∈V-S,(u,v)∈E}

2.S=S+{v};tot=tot+W(u,v);输出边(u,v)

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

c)        算法结束：tot为MST的总权值

注意：这里的Relax不同于求最短路径时的松弛操作。它的代码如下：

procedure relax(u,v,w:integer);        //松弛操作

begin

  if w<dis[v] then

    begin

      pre[v]:=u;

      dis[v]:=w;

    end;

end;

            可以看到，虽然不同，却也十分相似。

3)      算法优化：

                使用二叉堆(Binary Heap)来实现每步的DeleteMin(ExtractMin)操作

算法复杂度从O(V^2)降到O((V+E)㏒V)。推荐对稀疏图使用。

    使用Fibonacci Heap可以将复杂度降到O(E+V㏒V)，但因为编程复杂度太高，不推荐在信息学竞赛中使用。

    （不要问我为什么和Dijkstra一样……观察我的prim和dijkstra程序，会发现基本上只有relax和输出不一样……）