弗洛伊德算法仍从图的带权邻接矩阵cost 出发，其基本思想是：



    假设求从顶点vi到vj的最短路径，如果从vi到vj有弧，则从vi到vj存在一条长度为cost[I,j]的路径，该路径下一定是最短路径，尚需进行n次试探。首先考虑路径（vi ,v1,,vj）是否存在（即判别弧（vi ,v1,）和（v1,vj）是否存在）。如果存在，则比较（vi,vj）和（vi,v1,vj）的路径长`度取长度较短者为从vi 到vj的中间顶点的序号不大于1的最短路径。假如在路径上再增加一个顶点v2，也就是说，如果（v1 ,...,v2,）和（v2 ,...,v1）分别是当前找到的中间顶点的序号不大于1的最短路径，那么（v1 ,... v2, ,...vj ）就有可能是从vi到vj的中间顶点的序号不大于2的最短路径。将它和已经得到的从vi到vj中间顶点诒不大于1的最短路径相比较,从中选出间顶点的序号不大于2的最短路径之后，再增加一个顶点v3,继续进行试探。依次类推，在一般情况下，若（vi ,...,vk）和（vk,...,vj）分别是从vi到vk和从vk到vj的中间顶点的序号不大于k-1的最短路径，则将（vi ,... vk,...vj ）和已经得到的从vi到vj且中间顶点序号不大于k-1的最短路径相比较，其长度较短者便是从vi到vj的中间顶点的序号不大于k的最短路径。这样，在经过n次比较后，最后求得的必是从vi到vj的最短路径。按此方法，可以同时求得各对顶点间的最短路径。









问题：求任意两点间的最短路径。



①



②



③



④



⑤



⑥



1



2



2



3



4



4



1



7



8



9



























program  Floyd;



  const max=6;



  v:array[1..max,1..max] of integer=(( 0, 4, 8,99,99,99),



                                     ( 4, 0, 3, 4, 1,99),



                                     ( 8, 3, 0, 2, 2,99),



                                     (99, 4, 2, 0, 1, 7),



                                     (99, 1, 2, 1, 0, 9),



                                     (99,99,99, 7, 9, 0));



  var p:array[1..max,1..max] of integer; P:路径数组



      start,ending,i,j,k:integer;  START:始点, ENDING:终点



  procedure print(i,j:integer);  递归输出I到J的最短路径



    var k:integer;



    begin



      k:=p[i,j];



      if k<>0 then begin print(i,k);write(k,'=>');print(k,j);end;



    end;



  begin



    write('start,ending:');



    readln(start,ending);



    for i:=1 to max do for j:=1 to max do  p[i,j]:=0; 路径变量清零



    for k:=1 to max do   对V进行max次替换



        for i:=1 to max do



          for j:=1 to max do



if v[i,k]+v[k,j]<v[i,j] then  



若I经过K到J比I直接到J费用低则替换



begin v[i,j]:=v[i,k]+v[k,j];p[i,j]:=k;end;



P[I,J]表示I经过P[I,J]到J, P[I,J]=0表示I直接到J



    write(start,'=>');print(start,ending);writeln(ending);



  end.









p:任意两点路径    如何输出任意两点间路径：



  0  0  2  5  2  5  ①由P[1，6]=5知5为中间点



  0  0  0  5  0  5  ②由P[1，5]=2知2为（1，5）中间点



  2  0  0  0  0  4  ③由P[1，2]=0，P[2，5]=0知1至2，2至5为直达



  5  5  0  0  0  0  ④由P[5，6]=4知4为（5，6）中间点，而（5，4），（4，6）无中



  2  0  0  0  0  4  得路径为1→2→5→4→6                                间点



5        5  4  0  4  0  

同意楼上！

弗洛伊德算法
    弗洛伊德算法仍从图的带权邻接矩阵cost 出发，其基本思想是：
    假设求从顶点vi到vj的最短路径，如果从vi到vj有弧，则从vi到vj存在一条长度为cost[I,j]的路径，该路径下一定是最短路径，尚需进行n次试探。首先考虑路径（vi ,v1,,vj）是否存在（即判别弧（vi ,v1,）和（v1,vj）是否存在）。如果存在，则比较（vi,vj）和（vi,v1,vj）的路径长`度取长度较短者为从vi 到vj的中间顶点的序号不大于1的最短路径。假如在路径上再增加一个顶点v2，也就是说，如果（v1 ,...,v2,）和（v2 ,...,v1）分别是当前找到的中间顶点的序号不大于1的最短路径，那么（v1 ,... v2, ,...vj ）就有可能是从vi到vj的中间顶点的序号不大于2的最短路径。将它和已经得到的从vi到vj中间顶点诒不大于1的最短路径相比较,从中选出间顶点的序号不大于2的最短路径之后，再增加一个顶点v3,继续进行试探。依次类推，在一般情况下，若（vi ,...,vk）和（vk,...,vj）分别是从vi到vk和从vk到vj的中间顶点的序号不大于k-1的最短路径，则将（vi ,... vk,...vj ）和已经得到的从vi到vj且中间顶点序号不大于k-1的最短路径相比较，其长度较短者便是从vi到vj的中间顶点的序号不大于k的最短路径。这样，在经过n次比较后，最后求得的必是从vi到vj的最短路径。按此方法，可以同时求得各对顶点间的最短路径。


问题：求任意两点间的最短路径。







program  Floyd;
  const max=6;
  v:array[1..max,1..max] of integer=(( 0, 4, 8,99,99,99),
                                     ( 4, 0, 3, 4, 1,99),
                                     ( 8, 3, 0, 2, 2,99),
                                     (99, 4, 2, 0, 1, 7),
                                     (99, 1, 2, 1, 0, 9),
                                     (99,99,99, 7, 9, 0));
  var p:array[1..max,1..max] of integer; P:路径数组
      start,ending,i,j,k:integer;  START:始点, ENDING:终点
  procedure print(i,j:integer);  递归输出I到J的最短路径
    var k:integer;
    begin
      k:=p[i,j];
      if k<>0 then begin print(i,k);write(k,'=>');print(k,j);end;
    end;
  begin
    write('start,ending:');
    readln(start,ending);
    for i:=1 to max do for j:=1 to max do  p[i,j]:=0; 路径变量清零
    for k:=1 to max do   对V进行max次替换
        for i:=1 to max do
          for j:=1 to max do
if v[i,k]+v[k,j]<v[i,j] then  
若I经过K到J比I直接到J费用低则替换
begin v[i,j]:=v[i,k]+v[k,j];p[i,j]:=k;end;
P[I,J]表示I经过P[I,J]到J, P[I,J]=0表示I直接到J
    write(start,'=>');print(start,ending);writeln(ending);
  end.


p:任意两点路径    如何输出任意两点间路径：
  0  0  2  5  2  5  ①由P[1，6]=5知5为中间点
  0  0  0  5  0  5  ②由P[1，5]=2知2为（1，5）中间点
  2  0  0  0  0  4  ③由P[1，2]=0，P[2，5]=0知1至2，2至5为直达
  5  5  0  0  0  0  ④由P[5，6]=4知4为（5，6）中间点，而（5，4），（4，6）无中
  2  0  0  0  0  4  得路径为1→2→5→4→6                                间点
5    5  4  0  4  0

疑~~~~~~~~~怎么是一样的啊？！！！！！！！！！！！！！！！！！！！