最小树的算法
谁能给我解释一下有关digkstra的算法！！！！！！！！！！！谢谢啦！
图论：求最短路
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.
注：程序使用二叉堆
