当前位置:   article > 正文

Floyd算法求最短路径(附代码实例)_floyd算法求最短路径问题例题代码

floyd算法求最短路径问题例题代码

 

Floyd算法

使用范围:

1)求每对顶点的最短路径;

2)有向图、无向图和混合图;

算法思想:

      直接在图的带权邻接矩阵中用插入顶点的方法依次递推地构造出n个矩阵D(1), D(2), …, D(n), D(n)是图的距离矩阵, 同时引入一个后继点矩阵记录两点间的最短路径.

算法步骤:

d(i,j) : i到j的距离;

path(i,j): i到j的路径上i的后继点;

输入带权邻接矩阵a(i,j).

1)赋初值

对所有i,j, d(i,j)⬅a(i,j) , path(i,j)⬅j,k=l.

2)更新d(i,j) , path(i,j)

对所有i,j, 若d(i,k)+d(k,j)<d(i,j),则

d(i,j)⬅d(i,k)+d(k,j) , path(i,j)⬅path(i,k) , k ⬅k+1

3)重复2)直到k=n+1

 

使用说明:

Floyd算法程序的使用说明:

1.    [D, path]=floyd(a),  返回矩阵D, path 。其中a是所求图的带权邻接矩阵,D(i,j)表示i到j的最短距离;  path(i,j)表示i与j之间的最短路径上顶点i的后继点.

2.   [D, path, min1, path1]= floyd(a,i,j)   返回矩阵D, path;  并返回i与j之间的最短距离min1和最短路径path1.

 

MATLAB源码:

  1. function [D,path,min1,path1]=floyd(a,start,terminal)
  2. D=a;n=size(D,1);path=zeros(n,n);
  3. for i=1:n
  4. for j=1:n
  5. if D(i,j)~=inf
  6. path(i,j)=j;
  7. end, end, end
  8. for k=1:n
  9. for i=1:n
  10. for j=1:n
  11. if D(i,k)+D(k,j)<D(i,j)
  12. D(i,j)=D(i,k)+D(k,j);
  13. path(i,j)=path(i,k);
  14. end, end, end,end
  15. if nargin==3
  16. min1=D(start,terminal);
  17. m(1)=start;
  18. i=1;
  19. path1=[ ];
  20. while path(m(i),terminal)~=terminal
  21. k=i+1;
  22. m(k)=path(m(i),terminal);
  23. i=i+1;
  24. end
  25. m(i+1)=terminal;
  26. path1=m;
  27. end

示例:

  1. a =[ 0 2 8 1 Inf Inf Inf Inf Inf Inf Inf;
  2. 2 0 6 Inf 1 Inf Inf Inf Inf Inf Inf;
  3. 8 6 0 7 5 1 2 Inf Inf Inf Inf;
  4. 1 Inf 7 0 Inf Inf 9 Inf Inf Inf Inf;
  5. Inf 1 5 Inf 0 3 Inf 2 9 Inf Inf;
  6. Inf Inf 1 Inf 3 0 4 Inf 6 Inf Inf;
  7. Inf Inf 2 9 Inf 4 0 Inf 3 1 Inf;
  8. Inf Inf Inf Inf 2 Inf Inf 0 7 Inf 9;
  9. Inf Inf Inf Inf 9 6 3 7 0 1 2;
  10. Inf Inf Inf Inf Inf Inf 1 Inf 1 0 4;
  11. Inf Inf Inf Inf Inf Inf Inf 9 2 4 0];
  12. start = 1;
  13. terminal = 11;
  14. [D,path,min1,path1]=floyd(a,start,terminal)

结果:

  1. min1 =
  2. 13
  3. path1 =
  4. 1 2 5 6 3 7 10 9 11

 

声明:本文内容由网友自发贡献,不代表【wpsshop博客】立场,版权归原作者所有,本站不承担相应法律责任。如您发现有侵权的内容,请联系我们。转载请注明出处:https://www.wpsshop.cn/w/Guff_9hys/article/detail/797438
推荐阅读
相关标签
  

闽ICP备14008679号