求从任意一个顶点Vi出发,对给出的图,求到达任意顶点Vj（ij）的所有最短路径.
来源：学生作业帮助网 编辑：六六作业网 时间：2024/12/19 04:13:26
求从任意一个顶点Vi出发,对给出的图,求到达任意顶点Vj（ij）的所有最短路径.
求从任意一个顶点Vi出发,对给出的图,求到达任意顶点Vj（i<>j）的所有最短路径.
求从任意一个顶点Vi出发,对给出的图,求到达任意顶点Vj（ij）的所有最短路径.
const d:array[1..8,1..4] of byte=((2,3,4,0),(1,3,7,0),(1,2,4,5),(1,3,6,0),(3,6,7,8),(4,5,8,0),(2,5,8,0),(5,6,7,0));
n:array[1..8] of byte=(3,3,4,3,4,3,3,3);
var l,b:array[1..64] of byte;
f,r,h,m,st,ed,I,j,t,k,s,p,w:byte;
g:array[1..10] of byte;
e:array[1..8] of 0..1;
c:array[1..8,1..8]of byte;
bb:boolean;
begin
write('start:');readln(st);
write('end:');readln(ed);
fillchar(e,sizeof(e),0); {标记数组清零}
fillchar(c,sizeof(c),0); {路径数组清零}
f:=0;r:=1;
l[r]:=st;h:=1;w:=1;
bb:=true;
while bb do
begin
h:=h+1;g[h]:=r+1; {记录h+1层的首地址}
for i:=1 to w do
begin
f:=f+1;m:=l[f];e[m]:=1; {取队首结点,并设访问过标记}
for t:=1 to n[m] do {依次访问m结点的相邻结点}
if e[d[m,t]]=0 then {若m的相邻结点没有访问过}
begin
r:=r+1;l[r]:=d[m,t];b[r]:=f; {则进队列}
end;
end;
w:=r+1-g[h]; {计算第h层的新结点数目}
s:=0;
for k:=g[h] to r do {检查第h层上的新结点是否存在目标结点}
if l[k]=ed then {等于目标结点}
begin
s:=s+1;p:=b[k];j:=1;
c[s,j]:=L[k];
while p1 do
begin j:=j+1;c[s,j]:=L[p];p:=b[p]; end;
j:=j+1;c[s,j]:=L[p];
for t:=j downto 1 do
if t=1 then writeln(c[s,t]) else write(c[s,t],'->');
end;
if s0 then
begin
writeln(st,'->',ed);
writeln('total=',s,' step=',j-1);
bb:=false;
end;
end;
end.
什么情况