文件名称：基本算法（Dijkstra 算法和其它算法程序）
文件大小：36KB
文件格式：DOC
更新时间：2012-09-09 17:30:49
最小生成树 最短路径 Dijkstra
类似标号法，本质为贪心算法。 var a:array[1..maxn,1..maxn] of integer; b,pre:array[1..maxn] of integer; {pre[i]指最短路径上I的前驱结点} mark:array[1..maxn] of boolean; procedure dijkstra(v0:integer); begin fillchar(mark,sizeof(mark),false); for i:=1 to n do begin d[i]:=a[v0,i]; if d[i]< >0 then pre[i]:=v0 else pre[i]:=0; end; mark[v0]:=true; repeat {每循环一次加入一个离1集合最近的结点并调整其他结点的参数} min:=maxint; u:=0; {u记录离1集合最近的结点} for i:=1 to n do if (not mark[i]) and (d[i]< min) then begin u:=i; min:=d[i]; end; if u< >0 then begin mark[u]:=true; for i:=1 to n do if (not mark[i]) and (a[u,i]+d[u]< d[i]) then begin d[i]:=a[u,i]+d[u]; pre[i]:=u; end; end; until u=0; end;