欧阳建昭吧 关注:8贴子:81
  • 1回复贴,共1
弗洛伊德算法
    弗洛伊德算法仍从图的带权邻接矩阵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的最短路径



1楼2009-11-18 20:31回复
        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  
    


    2楼2009-11-18 20:31
    回复