15问答网 > 谁能举一个Pascal中Dijkstra算法求单源最短路径问题的例子并作一些说明

谁能举一个Pascal中Dijkstra算法求单源最短路径问题的例子并作一些说明

2025-02-13 07:49:30

推荐回答（4个）

回答1：

[问题分析]
对于一个含有n个顶点和e条边的图来说，从某一个顶点Vi到其余任一顶点Vj的最短路径，可能是它们之间的边（Vi，Vj），也可能是经过k个中间顶点和k+1条边所形成的路径(1≤k≤n-2)。下面给出解决这个问题的Dijkstra算法思想。
设图G用邻接矩阵的方式存储在GA中，GA[i,j]=maxint表示Vi，Vj是不关联的，否则为权值（大于0的实数）。设集合S用来保存已求得最短路径的终点序号，初始时S=[Vi]表示只有源点，以后每求出一个终点Vj，就把它加入到集合中并作为新考虑的中间顶点。设数组dist[1..n]用来存储当前求得的最短路径，初始时Vi，Vj如果是关联的，则dist[j]等于权值，否则等于maxint，以后随着新考虑的中间顶点越来越多，dist[j]可能越来越小。再设一个与dist对应的数组path[1..n]用来存放当前最短路径的边，初始时为Vi到Vj的边，如果不存在边则为空。
执行时，先从S以外的顶点（即待求出最短路径的终点）所对应的dist数组元素中，找出其值最小的元素（假设为dist[m]），该元素值就是从源点Vi到终点Vm的最短路径长度，对应的path[m]中的顶点或边的序列即为最短路径。接着把Vm并入集合S中，然后以Vm作为新考虑的中间顶点，对S以外的每个顶点Vj，比较dist[m]+GA[m,j]的dist[j]的大小，若前者小，表明加入了新的中间顶点后可以得到更好的方案，即可求得更短的路径，则用它代替dist[j]，同时把Vj或边（Vm，Vj）并入到path[j]中。重复以上过程n-2次，即可在dist数组中得到从源点到其余各终点的最段路径长度，对应的path数组中保存着相应的最段路径。

下面给出具体的Dijkstra算法框架（注：为了实现上的方便，用一个一维数组s[1..n]代替集合S，用来保存已求得最短路径的终点集合，即如果s[j]=0表示顶点Vj不在集合中，反之，s[j]=1表示顶点Vj已在集合中）。
Procedure Dijkstra(GA,dist,path,i)；
{表示求Vi到图G中其余顶点的最短路径，GA为图G的邻接矩阵，dist和path为变量型参数，
其中path的基类型为集合}
Begin
For j:=1 To n Do Begin {初始化}
If j<>i Then s[j]:=0 Else s[j]:=1；
dist[j]:=GA[i,j]；
If dist[j] End；
For k:=1 To n-2 Do
Begin
w:=maxint；m:=i；
For j:=1 To n Do {求出第k个终点Vm}
If (s[j]=0) and (dist[j] If m<>i Then s[m]:=1 else exit；
{若条件成立，则把Vm加入到S中，
否则退出循环，因为剩余的终点，其最短路径长度均为maxint，无需再计算下去}
For j:=1 To n Do {对s[j]=0的更优元素作必要修改}
If (s[j]=0) and (dist[m]+GA[m,j] Then Begin Dist[j]:=dist[m]+GA[m,j]；path[j]:=path[m]+[j]；End；
End；
End；

（1）从一个顶点到其余各顶点的最短路径
对于一个含有n个顶点和e条边的图来说，从某个顶点vi到其余任一顶点vj的最短路径，可能是它们之间的边（vi，vj），也可能是经过k个中间点和k+1条边所形成的路径（1≤k ≤n-2）。
首先来分析Dijkstra的算法思想
设图G用邻接矩阵的方式存储在GA中，GA[I，j]=maxint表示vi，vj是不关联的，否则为权值（大于0的实数）。设集合S用来存储保存已求得最短路径的终点序号，初始时S=[vi]表示只有源点，以后每求出一个终点vj，就把它加入到集合中并作为新考虑的中间顶点。设数组dist[1..n]用来存储当前求得的最短路径，初始时vi，vj如果是关联的，则dist[j]等于权值，否则等于maxint，以后随着新考虑的中间顶点越来越多，dist[j]可能越来越小。再设一个与dist对应的数组path[1..n]用来存放当前最短路径的边，初始时vi到vj的边，如果不存在边则为空。
执行时，先从S以外的顶点（即待求出最短路径的终点）所对应的dist数组元素中，找出其值最小的元素（假设为dist[m]），该元素值就是从源点vi到终点vm的最短路径长度，对应的path[m]中的顶点或边的序列即为最短路径。接着把vm并入集合S中，然后以vm作为新考虑的中间顶点，对S以外的每个顶点vj，比较dist[m]+GA[i，j]与dist[j]的大小，若前者小，表明加入了新的中间顶点后可以得到更好的方案，即可求得更短的路径，则用它代替dist[j]，同时把vj或边（vm，vj）并入到path[j]中。重复以上过程n-2次，即可在dist数组中得到从源点到其余个终点的最短路径长度，对应的path数组中保存着相应的最短路径。
为了实现上的方便，用一个一维数组s[1..n]代替集合s，用来保存已求得最短路径的终点集合，即如果s[j]=0表示顶点vj不在集合中，反之，s[j]表示顶点vj已在集合中）。

Procedure dijkstra (GA,dist path,I)
begin
for j:= 1 to n do begin
if j<>I then s[j]:=0;{j不在集合中} else s[j]:=1;{j在集合中}；
dist[j]:=GA[I,J];
IF dist [j]Then path [j]:=[I]+[j]
Else path[j]:=[ ];
End;
For k:= 1 to n-1 do begin w:=maxint;m:=I;
For j:= 1 to n do{求出第k个终点Vm}
if (s[j]=0)and(dist[j]If m<>I then s[m]:=1 else exit;{若条件成立，则把Vm加入到s中，否则退出循环，因为
剩余的终点，其最短路径长度均为maxint，无需再计算下去}
for j:=1 to n do {对s[j]=0的更优元素作必要修改}
if (s[j]=0)and (dist[m]+GA[m,j] then begin
dist[j]:=dist[m]+GA[m,j];
path[j]:=path[m]+[j];
End;
End;
End;

用集合的思想：

for k:=1 to n-1 do
begin
wm:=max;j:=0;
for i:=1 to n do
if not(i in s)and(dist[i] s:=s+[j];
for i:=1 to n do
if not(i in s)and(dist[j]+cost[j,i] begin dist[i]:=dist[j]+cost[j,i];path[i]:=path[j]+char(48+i);end;
end;

回答2：

解释一下吧
举一个简单的例子
设图
G（V，E）
（V是顶点集合，E是边集合）

顶点1 ---2--- 顶点2 ---3--- 顶点3
（无向图，关于无向图这一点，不理解也不影响）

这个时候
邻接矩阵
0 2 ∞
2 0 3
∞ 3 0
（∞ 表示无连接；0表示该边连接了两个相同的顶点,是不存在的）

此时，由图可以知道，实际上从1到3并不是无连接，可以通过顶点2，连接顶点3，之间的距离为5（2+3）。那么就可以在1-3之间直接创造一条边，权值为5。dijkstra算法以及其他SPFA，floyd求最短路径的算法都是用以上所举的思想为中心思想的。这种操作称作：松弛操作。

if V[i]+E[i,j] V[j]:=V[i]+E[i,j];

（其中V[i]表示目前源点到点i的最短距离，E是邻接矩阵)

对所有的顶点都进行一次对其他顶点的关于源点的松弛操作，就可以创造出源点到其他各个点最短边，并把源点到点i最短距离存储在V数组中

Const
maxn=??;

Var
i,j,n:longint;
E:Array[1..maxn,1..maxn]of longint;
V:Array[1..maxn]of longint;
Begin
Fillchar(E,sizeof(e),0);
Fillchar(V,sizeof(V),0);

Read(n);
For i:=1 to n do
For j:=1 to n do
Read(E[i,j]);

V[1]:=0;

For i:=1 to n do
For j:=2 to n do
if E[i,j]>0 then
if (V[i]+E[i,j] V[j]:=v[i]+E[i,j];

End.
(其中顶点1为源点）

回答3：

新手学spfa吧 spfa比较好懂只要会队列操作就行了用途比dij更广
这里有个我写的程序
var dis:array[1..2000] of longint;
e:array[1..2000,1..2000,1..2] of longint;
q:array[1..200000] of longint;
f:array[0..2000] of boolean;
rou:array[0..2000] of longint;
i,j,k,n:longint;

procedure spfa;
var l,r,i,j,k:longint;
begin
l:=1;
r:=1;
q[l]:=1;
dis[1]:=0;
while l<=r do
begin
for i:=1 to rou[q[l]] do
begin
k:=e[q[l],i,1];
if dis[k]>dis[q[l]]+e[q[l],i,2] then
begin
dis[k]:=dis[q[l]]+e[q[l],i,2];
if not(f[k]) then begin
inc(r);
q[r]:=k;
f[k]:=true; end;
end;
end;
f[q[l]]:=false;
inc(l);
end;
end;

procedure prepare;
var x,y,w:longint;
begin
readln(n);
readln(x,y,w);
for i:=1 to n do dis[i]:=maxlongint div 3;
while w<>0 do
begin
inc(rou[x]);
e[x,rou[x],1]:=y;
e[x,rou[x],2]:=w;
readln(x,y,w);
end;
end;

begin
prepare;
SPFA;
for i:=2 to n do
writeln(dis[i]);
end.

回答4：

可以看相关的OI论文，写的比较“通俗”。或者自己多看几遍，多实现几次，算是背吧，用的多了，思想慢慢就理解了，算法多写，其义自现

最新问答

从青岛火车站到海信大厦怎么走！坐几路公交车！

1995年农历6月18出生，阳历是？星座是？