最小树的算法 - 数据结构与算法

octillion

等　级：新手上路
帖　子：195
专家分：0
注　册：2008-7-24

第 2 楼

得分:0

dijkstra，提醒你一下，感叹号用在这里让别人看得不舒服。

图论：求最短路
1.    floyed算法在边权非负的有向图中计算每对顶点间的最短路径问题。该算法在图的传递闭包的基础上形成；
2.    Dijkstra算法在边权非负的有向图中计算单源最短路径问题。该算法建立在松弛技术基础之上；
3.    Bellman-Ford算法能在更一般的情况下解决单源点最短路径问题。所谓一般情况，指的是有向图的边权可以为负,但不允许存在负权回路。该算法亦是建立在松弛技术基础之上的；

Dijkstra算法
w[i,j]表示i,j的权
s[i,j]表示i到j的最短路
开始置源点检查标志
repeat
  i-检查过的点,j-未检查过的点,且min(w[i,j]),置j检查标志，此时j的最短路确定
  修改所有以j为起点的边，if s[o,j]+s[j,k]<s[o,k] then s[o,k]:=s[o,j]+s[j,k]
until 所有的点都检查过
注意，这种算法只适用于权没有负的情况下，时间复杂度O((n+e)log(2,n))，其中n是点数，e是边数
Dijkstra  的本质属于贪心
以下代码来自ASSL：

程序代码：

function Dijkstra: TKey;
var
    i: TIndex;
    Cur, Ptr: TIndex;
    Node: PFibonacciNode;
    Heap: TFibonacciHeap;
begin
    Heap.Create(N);
    for i := 1 to N do
    begin
        Check[i] := false;
        Heap.Insert(i, InfiniteValue);
        Dist[i] := InfiniteValue;
    end;
    Heap.DecreaseKey(S, 0);
    Dist[S] := 0;
    while not Check[T] do
    begin
        Node := Heap.Minimum;
        if Node = nil then Break;
        Cur := Node^.Index;

        Check[Cur] := true;
        Heap.DeleteMin;

        Ptr := Last[Cur];
        while Ptr > 0 do
        begin
            with Edge[Ptr] do
                if not Check[Adj] and (Dist[Adj] > Dist[Cur] + Weight) then
                begin
                    Dist[Adj] := Dist[Cur] + Weight;
                    Heap.DecreaseKey(Adj, Dist[Adj]);
                end;
            Ptr := Edge[Ptr].Prev;
        end;
    end;
    Result := Dist[T];
    Heap.Destory;
end;

function Dijkstra2: TKey;
var
    i: TIndex;
    Cur, Ptr: TIndex;
    Node: PBinaryNode;
    Heap: TBinaryHeap;
begin
    Heap.Create(N);
    for i := 1 to N do
    begin
        Check[i] := false;
        Heap.Insert(i, InfiniteValue);
        Dist[i] := InfiniteValue;
    end;
    Heap.DecreaseKey(S, 0);
    Dist[S] := 0;
    while not Check[T] do
    begin
        Node := Heap.Minimum;
        if Node = nil then Break;
        Cur := Node^.Index;

        Check[Cur] := true;
        Heap.DeleteMin;

        Ptr := Last[Cur];
        while Ptr > 0 do
        begin
            with Edge[Ptr] do
                if not Check[Adj] and (Dist[Adj] > Dist[Cur] + Weight) then
                begin
                    Dist[Adj] := Dist[Cur] + Weight;
                    Heap.DecreaseKey(Adj, Dist[Adj]);
                end;
            Ptr := Edge[Ptr].Prev;
        end;
    end;
    Result := Dist[T];
    Heap.Destory;
end;

function Dijkstra3: TKey;
var
    i: TIndex;
    Cur, Ptr: TIndex;
    Node: PPairNode;
    Heap: TPairHeap;
begin
    Heap.Create(N);
    for i := 1 to N do
    begin
        Check[i] := false;
        Heap.Insert(i, InfiniteValue);
        Dist[i] := InfiniteValue;
    end;
    Heap.DecreaseKey(S, 0);
    Dist[S] := 0;
    while not Check[T] do
    begin
        Node := Heap.Minimum;
        if Node = nil then Break;
        Cur := Node^.Index;

        Check[Cur] := true;
        Heap.DeleteMin;

        Ptr := Last[Cur];
        while Ptr > 0 do
        begin
            with Edge[Ptr] do
                if not Check[Adj] and (Dist[Adj] > Dist[Cur] + Weight) then
                begin
                    Dist[Adj] := Dist[Cur] + Weight;
                    Heap.DecreaseKey(Adj, Dist[Adj]);
                end;
            Ptr := Edge[Ptr].Prev;
        end;
    end;
    Result := Dist[T];
    Heap.Destory;
end;

1)    适用条件&范围：
a)    单源最短路径(从源点s到其它所有顶点v);
b)    有向图&无向图(无向图可以看作(u,v),(v,u)同属于边集E的有向图)
c)    所有边权非负(任取(i,j)∈E都有Wij≥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,Wu,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)。

程序代码：

{
单源最短路径的Dijkstra算法。

使用二叉堆挑选
总复杂度O((e+v)logv)
}
const
  maxn=100;
type
  link=^node;      //邻接表类型
  node=record
         v,w    :integer;
         next   :link;
       end;
  htype=record          //堆节点
          v,d,p :integer;
        end;
var
  n,s,hl        :integer;     //顶点数；源点；堆长度
  heap          :array[0..maxn]of htype;
  hpos          :array[1..maxn]of integer;   //hpos[v]:顶点v在堆中的位置
  g             :array[1..maxn]of link;    //邻接表

procedure insert(u,v,w:integer);      //将权值为w的边(u,v)插入到邻接表
var
  x     :link;
begin
  new(x);
  x^.v:=v; x^.w:=w;
  x^.next:=g[u]; g[u]:=x;
end;

procedure init;        //初始化
var
  u,v,w :integer;
begin
  assign(input,'g.in');reset(input);
  readln(n,s);
  while not eof do
    begin
      readln(u,v,w);
      insert(u,v,w);insert(v,u,w);
    end;
end;

procedure swap(a,b:integer);           //交换堆中下标为a,b的节点
begin
  heap[0]:=heap[a];heap[a]:=heap[b];heap[b]:=heap[0];
  hpos[heap[a].v]:=a;hpos[heap[b].v]:=b;
end;

procedure decrease(i:integer);         //减小键值并恢复堆性质
begin
  while (i<>1)and(heap[i].d<heap[i div 2].d) do
    begin
      swap(i,i div 2);
      i:=i div 2;
    end;
end;

procedure heapfy;        //恢复堆性质
var
  i     :integer;
begin
  i:=2;
  while i<=hl do
    begin
      if(i<hl)and(heap[i+1].d<heap[i].d) then inc(i);
      if heap[i].d<heap[i div 2].d then
        begin
          swap(i,i div 2);
          i:=i*2;
        end
      else break
    end;
end;

procedure relax(u,v,w:integer);       //松弛操作
begin
  if w+heap[hpos[u]].d<heap[hpos[v]].d then
    begin
      heap[hpos[v]].p:=u;
      heap[hpos[v]].d:=w+heap[hpos[u]].d;
      decrease(hpos[v]);
    end;
end;

procedure dijkstra;          //主过程
var
  u     :integer;
  p     :link;
begin
  for u:=1 to n do         //初始化堆
    begin
      heap[u].v:=u;
      heap[u].d:=maxint;
      hpos[u]:=u;
    end;

  heap[s].p:=s;heap[s].d:=0;swap(1,s);
  hl:=n;
  while hl>0 do
    begin
      u:=heap[1].v;
      swap(1,hl);dec(hl);heapfy;     //将堆的根节点移出堆并恢复堆性质
      p:=g[u];
      while p<>nil do
        begin
          if hpos[p^.v]<=hl then relax(u,p^.v,p^.w);   //对与u邻接且在堆中的顶点进行松弛操作
          p:=p^.next;
        end;
    end;
end;

procedure path(i:integer);
begin
  if heap[hpos[i]].p<>s then path(heap[hpos[i]].p);
  write('-->',i);
end;

procedure show;
var
  i     :integer;
begin
  for i:=1 to n do
    begin
      write(i:3,':',heap[hpos[i]].d:3,':',s);
      path(i);        //递归输出路径
      writeln;
    end
end;
{==========main===========}
begin
init;
dijkstra;
show;
end.
注：程序使用二叉堆

2008-08-04 11:58

妍清舞

等　级：新手上路
帖　子：121
专家分：0
注　册：2007-11-12

第 4 楼

得分:0

Dijkstra算法是用来求最短路径的吧，还有Floyd算法
求最小生成树的是Prim算法、Kruskal算法

2008-08-04 14:46