永发信息网

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

给个测试数据,这样好检查

我要举报
如以上回答内容为低俗、色情、不良、暴力、侵权、涉及违法等信息,可以点下面链接进行举报!
点此我要举报以上问答信息
大家都在看
推荐资讯