Floyd最短路算法

Halcom

Floyd最短路算法

1. clc                               % 清屏
   
2. clear all;                          % 删除workplace变量
   
3. close all;                          % 关掉显示图形窗口
   
4. clc,clear,close all
   
5. x7=[0 1 inf inf inf 2;      %D0
   
6. 1 0 4 inf inf 4;
   
7. inf 4 0 2 inf 1;
   
8. inf inf 2 0 3 3;
   
9. inf inf inf 3 0 5;
   
10. 2 4 1 3 5 0];
    
11. n=length(x7);
    
12. path=zeros(n);
    
13. %flord最小距离法
    
14. for k=1:n
    
15.     for i=1:n
    
16.         for j=1:n
    
17.             if x7(i,j)>x7(i,k)+x7(k,j)     % 节点直接连接大于中间插入的节点时
    
18.                 x7(i,j)=x7(i,k)+x7(k,j);  % 记录更新
    
19.                 path(i,j)=k;           % 路由号记录
    
20.             end
    
21.         end
    
22.     end
    
23. end   
    
24. x7
    
25. path

复制代码

输出：

1. x7 =
   
2. 
   
3.      0     1     3     5     7     2
   
4.      1     0     4     6     8     3
   
5.      3     4     0     2     5     1
   
6.      5     6     2     0     3     3
   
7.      7     8     5     3     0     5
   
8.      2     3     1     3     5     0
   
9. 
   
10. 
    
11. path =
    
12. 
    
13.      0     0     6     6     6     0
    
14.      0     0     0     3     6     1
    
15.      6     0     0     0     4     0
    
16.      6     3     0     0     0     0
    
17.      6     6     4     0     0     0
    
18.      0     1     0     0     0

复制代码