比特138

 找回密码
 立即注册
搜索
查看: 81|回复: 0

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

[复制链接]

518

主题

518

帖子

105

积分

初级会员

Rank: 2

金币
105
发表于 2020-6-5 10:43:47 | 显示全部楼层 |阅读模式
实验一 弗洛伊德算法
实验目的:弗洛伊德算法求最短路径
实验内容:
  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.     int j;  
  17.     for(i = 1 ; i < n ; ++i)//对除源点的每一个点进行最短计算
  18.     {
  19.     int min = INF;  //记录最小len[i]
  20.     int pos;  //记录小len[i] 的点
  21.       for(j = 1 ; j <= n ; ++j)
  22.       {     

  23.             if(!visit[j] && min > len[j])
  24.             {
  25.                 pos = j;  
  26.                 min = len[j];  
  27.             }  
  28.       }  
  29.         visit[pos] = 1;  
  30.          for(j = 1 ; j <= n ; ++j)
  31.          {
  32.             if(!visit[j] && (len[j] > (len[pos] +map[pos][j])))
  33.             { //如果j节点没有被访问过&&j节点到源节点的最短路径>pos节点到源节点的最短路径+pos节点到j节点的路径  

  34.                 len[j] = len[pos] + map[pos][j];    //更新j节点到源节点的最短路径   
  35.             }  
  36.          }  
  37.     }  
  38.     return len[to];

  39. }
  40.     int main ()
  41. {  
  42.     int i,j;  
  43.   //  scanf("%d%d",&n,&m);    //输入数据
  44.     n = 6;    //测试数据
  45.     m = 9;
  46.     for(i = 1 ; i <= n ; ++i)
  47.     {    //设一开始每个点都不可达
  48.         for(j = 1 ; j <= n ; ++j)
  49.         {  
  50.             map[i][j] = INF;  
  51.         }  
  52.     }     
  53. /*    int a,b,c;    //输入数据

  54.     for(i = 1 ; i <= m ; ++i)
  55.     {  
  56.     scanf("%d%d%d",&a,&b,&c);  
  57.     map[a][b] = map[b][a] = c;  
  58.     }  */
  59.     map[1][2] = 5;    //测试数据
  60.     map[1][3] = 8;
  61.     map[1][6] = 3;
  62.     map[1][4] = 7;
  63.     map[2][3] = 4;
  64.     map[3][6] = 9;
  65.     map[4][6] = 6;
  66.     map[5][6] = 1;
  67.     map[4][5] = 5;
  68.     map[3][4] = 5;
  69.     int temp = INF;
  70.     for(i = 1 ; i <= n ; ++i)
  71.     {
  72.       for(j = 1 ; j <= n ; ++j)
  73.       {
  74.     if(map[i][j] == temp)
  75.     map[i][j] = map[j][i];
  76.       }
  77.     }
  78.     int ans = dijkstra(1,5);  
  79.     printf("%d",ans);  
  80.     return 0;  
  81. }
复制代码
/* 边的数据
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
*/

回复

使用道具 举报

您需要登录后才可以回帖 登录 | 立即注册

本版积分规则

手机版|小黑屋|比特138 |网站地图

GMT+8, 2020-11-28 10:23 , Processed in 0.062152 second(s), 7 queries , Redis On.

Powered by Discuz! X3.4

Copyright © 2001-2020, Tencent Cloud.

快速回复 返回顶部 返回列表