弗洛伊德算法和迪杰斯特拉算法求最短路径 C语言源程序

实验一 弗洛伊德算法
实验目的：弗洛伊德算法求最短路径
实验内容：

1. #include <stdio.h>
   
2. void main()
   
3. {
   
4.     int e[9][9],k,i,j,n,m,t1,t2,t3;
   
5.     int inf=99999999; //用inf(infinity的缩写)存储一个我们认为的正无穷值
   
6.     scanf("%d %d",&n,&m);//读入n和m，n表示顶点个数，m表示边的条数
   
7.     //初始化
   
8.     for(i=1;i<=n;i++)
   
9.         for(j=1;j<=n;j++)
   
10.             if(i==j) e[i][j]=0;  
    
11.               else e[i][j]=inf;
    
12.     //读入边
    
13.     for(i=1;i<=m;i++)
    
14.     {
    
15.         scanf("%d %d %d",&t1,&t2,&t3);
    
16.         e[t1][t2]=t3;
    
17.     }
    
18.     for(k=1;k<=n;k++)
    
19.         for(i=1;i<=n;i++)
    
20.             for(j=1;j<=n;j++)
    
21.                 if(e[i][j]>e[i][k]+e[k][j] )
    
22.                     e[i][j]=e[i][k]+e[k][j];
    
23.     for(i=1;i<=n;i++)
    
24.     {
    
25.      for(j=1;j<=n;j++)
    
26.         {
    
27.             printf("%10d",e[i][j]);
    
28.         }
    
29.         printf("\n");
    
30.     }
    
31.    
    
32. }

复制代码

/* 测试数据 n=4 m=5
边的数据
1 2 5
1 3 6
2 3 1
2 4 4
3 4 4
输出结果
0          5          6           9
99999999   0          1           4
99999999   99999999   0           4
99999999   99999999   99999999    0

*/

实验一 迪杰斯特拉算法
实验目的：迪杰斯特拉算法求最短路径
实验内容：

1. #include<stdio.h>
   
2. #define SIZE 110  
   
3. #define INF 1000000;  
   
4. int map[SIZE][SIZE];    //邻接矩阵存储
   
5. int len[SIZE];         //d[i]表示源点到i这个点的距离
   
6. int visit[SIZE];      //节点是否被访问
   
7. int n,m;  
   
8. int dijkstra(int from, int to)//从源点到目标点
   
9. {                     
   
10.     int i;  
    
11.     for(i = 1 ; i <= n ; i ++)//初始化
    
12.     {     
    
13.         visit[i] = 0;    //一开始每个点都没被访问
    
14.         len[i] = map[from][i];    //先假设源点到其他点的距离
    
15. 
    
16.     }  
    
17.     int j;  
    
18.     for(i = 1 ; i < n ; ++i)//对除源点的每一个点进行最短计算
    
19.     {
    
20.     int min = INF;  //记录最小len[i]
    
21.     int pos;  //记录小len[i] 的点
    
22.       for(j = 1 ; j <= n ; ++j)
    
23.       {     
    
24. 
    
25.             if(!visit[j] && min > len[j])
    
26.             {
    
27.                 pos = j;  
    
28.                 min = len[j];  
    
29.             }  
    
30.       }  
    
31.         visit[pos] = 1;  
    
32.          for(j = 1 ; j <= n ; ++j)
    
33.          {
    
34.             if(!visit[j] && (len[j] > (len[pos] +map[pos][j])))
    
35.             { //如果j节点没有被访问过&&j节点到源节点的最短路径>pos节点到源节点的最短路径+pos节点到j节点的路径  
    
36. 
    
37.                 len[j] = len[pos] + map[pos][j];    //更新j节点到源节点的最短路径   
    
38.             }  
    
39.          }  
    
40.     }  
    
41.     return len[to];
    
42. 
    
43. }
    
44.     int main ()
    
45. {  
    
46.     int i,j;  
    
47.   //  scanf("%d%d",&n,&m);    //输入数据
    
48.     n = 6;    //测试数据
    
49.     m = 9;
    
50.     for(i = 1 ; i <= n ; ++i)
    
51.     {    //设一开始每个点都不可达
    
52.         for(j = 1 ; j <= n ; ++j)
    
53.         {  
    
54.             map[i][j] = INF;  
    
55.         }  
    
56.     }     
    
57. /*    int a,b,c;    //输入数据
    
58. 
    
59.     for(i = 1 ; i <= m ; ++i)
    
60.     {  
    
61.     scanf("%d%d%d",&a,&b,&c);  
    
62.     map[a][b] = map[b][a] = c;  
    
63.     }  */
    
64.     map[1][2] = 5;    //测试数据
    
65.     map[1][3] = 8;
    
66.     map[1][6] = 3;
    
67.     map[1][4] = 7;
    
68.     map[2][3] = 4;
    
69.     map[3][6] = 9;
    
70.     map[4][6] = 6;
    
71.     map[5][6] = 1;
    
72.     map[4][5] = 5;
    
73.     map[3][4] = 5;
    
74.     int temp = INF;
    
75.     for(i = 1 ; i <= n ; ++i)
    
76.     {
    
77.       for(j = 1 ; j <= n ; ++j)
    
78.       {
    
79.     if(map[i][j] == temp)
    
80.     map[i][j] = map[j][i];
    
81.       }
    
82.     }
    
83.     int ans = dijkstra(1,5);  
    
84.     printf("%d",ans);  
    
85.     return 0;  
    
86. }

复制代码

/* 边的数据
1 2 5
1 3 8
1 6 3
1 4 7
2 3 4
3 6 9
5 6 1
4 5 5
3 4 5
*/

【必读】版权免责声明

1、本主题所有言论和内容纯属会员个人意见，与本论坛立场无关。2、本站对所发内容真实性、客观性、可用性不做任何保证也不负任何责任，网友之间仅出于学习目的进行交流。3、对提供的数字内容不拥有任何权利，其版权归原著者拥有。请勿将该数字内容进行商业交易、转载等行为，该内容只为学习所提供，使用后发生的一切问题与本站无关。 4、本网站不保证本站提供的下载资源的准确性、安全性和完整性;同时本网站也不承担用户因使用这些下载资源对自己和他人造成任何形式的损失或伤害。 5、本网站所有软件和资料均为网友推荐收集整理而来，仅供学习用途使用，请务必下载后两小时内删除，禁止商用。6、如有侵犯你版权的，请及时联系我们（电子邮箱1370723259@qq.com）指出，本站将立即改正。