首页 > 代码库 > ACM训练-floyd算法

ACM训练-floyd算法

2024-09-08 17:51:15   218人阅读

问题描述：多源点问题和负权值图的最短路径

算法描述：Floyd算法是一个经典的动态规划算法。从任意节点i到任意节点j的最短路径不外乎2种可能，1是直接从i到j，2是从i经过若干个节点k到j。所以，我们假设Dis(i,j)为节点u到节点v的最短路径的距离，对于每一个节点k，我们检查Dis(i,k) + Dis(k,j) < Dis(i,j)是否成立，如果成立，证明从i到k再到j的路径比i直接到j的路径短，我们便设置Dis(i,j) = Dis(i,k) + Dis(k,j)，这样一来，当我们遍历完所有节点k，Dis(i,j)中记录的便是i到j的最短路径的距离。

源代码：

 1 #include<stdio.h>
 2 #define MAX 100000
 3 int main()
 4 {
 5     int n;
 6     int arcs[10][10],path[10][10];//pat[i][j]=k 表示从i到j会经过k  
 7     FILE *fp=fopen("floyd_data.txt","r");
 8     if(fp==NULL)
 9     {
10         printf("open file error\n");
11         return 0;
12     } 
13     scanf("%d",&n);
14     for(int i=0;i<n;i++)
15     {
16         for(int j=0;j<n;j++)
17         {
18             fscanf(fp,"%d",&arcs[i][j]);
19             path[i][j]=j; //初始化 
20         }
21     }
22     for(int k=0;k<n;k++)
23     for(int i=0;i<n;i++)
24     for(int j=0;j<n;j++)
25     if(arcs[i][k]+arcs[k][j]<arcs[i][j]) 
26     {
27         arcs[i][j]=arcs[i][k]+arcs[k][j];
28         path[i][j]=k;
29     }
30     for(int i=0;i<n;i++)
31     {
32         for(int j=0;j<n;j++)
33         {
34             printf("%d->%d:%d    ",i,j,arcs[i][j]);
35             int t=i;
36             while(t!=j)
37             {
38                 printf("%d--",t);
39                 t=path[t][j];
40             }  
41             printf("%d",t);
42             printf("\n");
43         }
44                 
45     }
46     if(fclose(fp)!=0) printf(" close file error\n");
47 }

时间复杂度：O（n3）

ACM训练-floyd算法


联系
我们