pascal编写的floyd算法求两点间的最短路径
答案:3 悬赏:10 手机版
解决时间 2021-08-12 10:59
- 提问者网友:蓝莓格格巫
- 2021-08-11 10:25
我的程序:
program floyd;
var
k,n,i,j,x,max:integer;
a:array[1..5,1..5]of integer;
path:array[1..5,1..5]of integer;
procedure print(i,j:integer); 输出vi到vj最短路径的顶点序列
var k:integer;
begin
k:=path[i,j];
if k<>0 then
begin
print(i,k);
write(k);
print(k,j);
end;
end;
begin
assign(input,'floyd.in');
reset(input);
assign(output,'floyd.out');
rewrite(output);
readln(n);
max:=maxint;
for i:=1 to n do //初始化邻接矩阵
begin
for j:=1 to n do
begin
read(x);
if x<>0 then a[i,j]:=x else
if (x=0) and (i=j) then a[i,j]:=x else a[i,j]:=maxint;
end;
readln;
end;
for i:=1 to n do //初始化path
for j:=1 to n do
if (a[i,j]<>0) and (a[i,j]<>maxint) then path[i,j]:=i;
for k:=1 to n do 枚举加入图中的每个点
for i:=1 to n do
for j:=1 to n do
if (a[i,j]<>0) and (j<>k) and (i<>k) and (a[i,k]<>max) and (a[k,j]<>max) then
if (a[i,j]>a[i,k]+a[k,j]) then
begin
a[i,j]:=a[i,k]+a[k,j]; 更新顶点i到j的最短路
path[i,j]:=k;
end;
for i:=1 to n do
begin
for j:=1 to n do
if a[i,j]=max then write(0:4) else write(a[i,j]:4);
writeln;
end;
print(2,5); 递归求出v2到v5最短路的顶点序列
close(input);
close(output);
end.
问题:我把子过程去掉的话,程序运行输出a[i,j]的最短路径结果是正确的,但我把输出的子程序加进去之后,编译的时候会栈溢出 stack overflow error 请问是怎么一回事呢?请高手不吝赐教~~~~
最佳答案
- 五星知识达人网友:夜余生
- 2021-08-11 10:38
//我的程序:
program floyd;
var
k,n,i,j,x,max:integer;
a:array[1..5,1..5]of integer;
path:array[1..5,1..5]of integer;
procedure print(i,j:integer); //输出vi到vj最短路径的顶点序列
var k:integer;
begin
k:=path[i,j];
if k=0 then exit;
print(i,k);
write(' ',k);
print(k,j);
end;
begin
assign(input,'floyd.in');reset(input);
assign(output,'floyd.out');rewrite(output);
readln(n);
max:=maxint;
for i:=1 to n do //初始化邻接矩阵
begin
for j:=1 to n do
begin
read(x);
if x<>0 then a[i,j]:=x else
if (x=0) and (i=j) then a[i,j]:=x else a[i,j]:=maxint;
end;
readln;
end;
{ for i:=1 to n do //初始化path
for j:=1 to n do
if (a[i,j]<>0) and (a[i,j]<>maxint) then path[i,j]:=i; } 把初始化删掉,不然会死循环。
for k:=1 to n do //枚举加入图中的每个点
for i:=1 to n do
for j:=1 to n do
if (a[i,j]<>0) and (j<>k) and (i<>k) and (a[i,k]<>max) and (a[k,j]<>max) then
if (a[i,j]>a[i,k]+a[k,j]) then
begin
a[i,j]:=a[i,k]+a[k,j]; // 更新顶点i到j的最短路
path[i,j]:=k;
end;
for i:=1 to n do
begin
for j:=1 to n do
if a[i,j]=max then write(0:4) else write(a[i,j]:4);
writeln;
end;
write(2);print(2,5);writeln(' ',5); //递归求出v2到v5最短路的顶点序列
close(input);
close(output);
end.
全部回答
- 1楼网友:醉吻情书
- 2021-08-11 12:36
program floyd; var k,n,i,j,x,max:integer; a:array[1..5,1..5]of integer; path:array[1..5,1..5]of integer;
procedure print(i,j:integer); var k:integer; begin k:=path[i,j]; if k > 0 then begin print(i,path[i,k]); print(k,j); end; if k = -1 then write(i,j); end;
begin readln(n); max:=maxint; for i:=1 to n do //初始化邻接矩阵 begin for j:=1 to n do begin read(x); if x<>0 then a[i,j]:=x else if (x=0) and (i=j) then a[i,j]:=x else a[i,j]:=maxint; end; end; for i:=1 to n do for j:=1 to n do if (a[i,j]<>0) and (a[i,j]<>maxint) then path[i,j]:=-1 else path[i,j]:= 0;
for k:=1 to n do for i:=1 to n do for j:=1 to n do if (a[i,j]<>0) and (j<>k) and (i<>k) and (a[i,k]<>max) and (a[k,j]<>max) then if (a[i,j]>a[i,k]+a[k,j]) then begin a[i,j]:=a[i,k]+a[k,j]; path[i,j]:=k; end; for i:=1 to n do begin for j:=1 to n do write(path[i,j]:4); writeln; end;print(2,5);close(input);close(output);end.你的输出有问题;你想想4-5是可以直接到的你这样一稿4 -5 分成 4 - 4 和 4 - 5就挂了
- 2楼网友:纵马山川剑自提
- 2021-08-11 11:00
我要举报
如以上回答内容为低俗、色情、不良、暴力、侵权、涉及违法等信息,可以点下面链接进行举报!
点此我要举报以上问答信息
大家都在看
推荐资讯