最短路径（佛洛依德算法-floyed）

奥普瓯江

原理：




备注：




算法：

1. #include <stdio.h>
   
2. #include <stdlib.h>
   
3. 
   
4. #define MAX 65535
   
5. 
   
6. int KA[4][4] = {{0, 2, 6, 4}, {MAX, 0, 3, MAX}, {7, MAX, 0, 1}, {5, MAX, 12, 0}};
   
7. 
   
8. 
   
9. int main()
   
10. {
    
11.     //佛洛依德算法需要经过3个for循环第一个
    
12. 
    
13.     for(int k = 0; k < 4; k++)          //这个循环是他经过的那个节点
    
14.     {
    
15.         for(int i = 0; i < 4; i++)      //从经过的那个节点开始横向比较
    
16.         {
    
17.            for(int j = 0; j < 4; j++)   //从经过的那个节点开始竖向比较
    
18.            {
    
19.                if((i != j) && (i != k) && (j != k) &&  KA[i][j] > KA[i][k] + KA[k][j])      //比较的前提是i不等于j、i不等于k、j不等于k，总体含义是自己不等于自己，这可以减少运算，然后才是判断竖排的数与横向的数相加是否小于没格循环的数如果小于那就执行，替换掉i-j单元中的数据
    
20.                {
    
21.                    KA[i][j] = KA[i][k] + KA[k][j];                                          //数据替换
    
22.                }
    
23. 
    
24.            }
    
25.         }
    
26. 
    
27.     }
    
28. 
    
29.     for(int i = 0; i < 4; i++)
    
30.     {
    
31.         for(int j = 0; j < 4; j++)
    
32.         {
    
33.             printf("%d ", KA[i][j]);
    
34.         }
    
35.         putchar('\n');
    
36.     }
    
37. 
    
38. 
    
39. 
    
40.     return 0;
    
41. }
    

复制代码

输出结果：

yinda_peng

顶，离散数学知识