迪杰斯特拉算法的算法实现
发布网友
发布时间：2022-04-28 21:24
共2个回答
热心网友
时间：2022-04-08 05:25
下面是该算法的Pascal程序 typebool=array[1..10]ofboolean;arr=array[0..10]ofinteger;vara:array[1..10,1..10]ofinteger;//存储图的邻接数组，无边为10000c,d,e:arr;//c为最短路径数值,d为各点前趋,t:bool;//e：路径，t为辅助数组i,j,n,m:integer;inf,outf:text;procereinit;//不同题目邻接数组建立方式不一样beginassign(inf,inputfile);assign(outf,outputfile);reset(inf);rewrite(outf);read(inf,n);fori:=1tondobeginforj:=1tondobeginread(inf,a[i,j]);ifa[i,j]=0thena[i,j]:=10000;end;end;end;proceredijkstra(qi:integer;t:bool;varc{,d}:arr);//qi起点,{}中为求路径部分,不需求路径时可以不要vari,j,k,min:integer;begint[qi]:=true;//t数组一般在调用前初始,除起点外所有节点都化成false,也可将部分点初始化成true以回避这些点fori:=1tondod[i]:=qi;d[qi]:=0;fori:=1tondoc[i]:=a[qi,i];fori:=1ton-1dobeginmin:=maxint;//改为最大值forj:=1tondoif(c[j]<min)andnott[j]thenbegink:=j;min:=c[j];end;t[k]:=true;forj:=1tondoif(c[k]+a[k,j]<c[j])andnott[j]thenbeginc[j]:=c[k]+a[k,j];d[j]:=k;end;end;end;proceremake(zh:integer;d:arr;vare:arr);//生成路径,e[0]保存路径vari,j,k:integer;//上的节点个数begini:=0;whiled[zh]<>0dobegininc(i);e[i]:=zh;zh:=d[zh];end;inc(i);e[i]:=qi;e[0]:=i;end;主程序调用：求长度：初始化t，然后dijkstra(qi,t,c,d)
求路径：make(m,d,e) ，m是终点 1. 将与源点相连的点加入堆，并调整堆。
2. 选出堆顶元素u（即代价最小的元素），从堆中删除，并对堆进行调整。
3. 处理与u相邻的，未被访问过的，满足三角不等式的顶点
1):若该点在堆里，更新距离，并调整该元素在堆中的位置。
2):若该点不在堆里，加入堆，更新堆。
4. 若取到的u为终点，结束算法；否则重复步骤2、3。 procereDijkstra;varu,v,e,i:longint;beginfillchar(dis,sizeof(dis),$7e);//距离fillchar(Inh,sizeof(Inh),false);//是否在堆中fillchar(visit,sizeof(visit),false);//是否访问过size:=0;e:=last[s];whilee<>0do//步骤1beginu:=other[e];ifnot(Inh[u])then//不在堆里begininc(size);heap[size]:=u;dis[u]:=cost[e];Loc[u]:=size;//Loc数组记录元素在堆中的位置Inh[u]:=true;Shift_up(Loc[u]);//上浮endelseifcost[e]<dis[u]then//在堆里begindis[u]:=cost[e];Shift_up(Loc[u]);Shift_down(Loc[u]);end;e:=pre[e];end;visit[s]:=true;whiletruedobeginu:=heap[1];//步骤2ifu=tthenbreak;//步骤4visit[u]:=true;heap[1]:=heap[size];dec(size);Shift_down(1);e:=last[u];whilee<>0do//步骤3beginv:=other[e];ifNot(visit[v])and(dis[u]+cost[e]<dis[v])then//与u相邻的，未被访问过的，满足三角不等式的顶点ifInh[v]then//在堆中begindis[v]:=dis[u]+cost[e];Shift_up(Loc[v]);Shift_Down(Loc[v]);endelse//不再堆中begininc(size);heap[size]:=v;dis[v]:=dis[u]+cost[e];Loc[v]:=size;Inh[v]:=true;Shift_up(Loc[v]);end;e:=pre[e];end;end;writeln(dis[t]);end;
热心网友
时间：2022-04-08 06:43
设给定源点为Vs，S为已求得最短路径的终点集，开始时令S={Vs} 。当求得第一条最短路径(Vs ，Vi)后，S为{Vs，Vi} 。根据以下结论可求下一条最短路径。
设下一条最短路径终点为Vj ，则Vj只有：
◆ 源点到终点有直接的弧<Vs，Vj>；
◆ 从Vs 出发到Vj 的这条最短路径所经过的所有中间顶点必定在S中。即只有这条最短路径的最后一条弧才是从S内某个顶点连接到S外的顶点Vj 。
若定义一个数组dist[n]，其每个dist[i]分量保存从Vs 出发中间只经过集合S中的顶点而到达Vi的所有路径中长度最小的路径长度值，则下一条最短路径的终点Vj必定是不在S中且值最小的顶点，即：
dist[i]=Min{ dist[k]| Vk∈V-S }
利用上述公式就可以依次找出下一条最短路径。
· 示例程序
· 算法思想
var a:array[1..100,1..100]of integer;//邻接矩阵
flag:array[1..100] of boolean;//已经找到最短路径的节点标志
path:array[1..100]of integer;
w,x,n,i,j,min,minn,k:integer;
begin
readln(n,k);for i:=1 to n do//读取邻接矩阵,无路径写-1
begin
for j:=1 to n do
begin
read(a[i,j]);
If a[i,j]=-1 then a[I,j]:=maxint;
end;
readln;
end;
fillchar(flag,sizeof(flag),false);//标明所有节点都未找到最短路径
flag[k]:=true; //源节点除外
fillword(path,sizeof(path) div 2,k);
path[k]:=0;
minn:=k;//标记最小的点for x:=2 to n do
begin
min:=32767;//标记要找下一个最短路径点的距离
for i:=1 to n do//找下一点点
if (a[k,i]<min) and (flag[i]=false) then
begin
min:=a[k,i];
minn:=i;
end;
flag[minn]:=true;//标记下一个点的找到
for j:=1 to n do //更新最短路径
if (j<>minn) and (a[k,minn]+a[minn,j]<a[k,j]) and (flag[j]=false) then
begin
a[k,j]:=a[k,minn]+a[minn,j];
path[j]:=minn;
end;
end;
for i:=1 to n do write(a[k,i],' ');//输出源点到各个点的距离
writeln;
for i:=1 to n do write(path[i],' ');//输出源点到各个点的距离
end.
求采纳（空格被百度吃了……）
