实现迪杰斯特拉算法求某个源点到其余个点_迪杰斯特拉算法应用举例

实现迪杰斯特拉算法求某个源点到其余个点_迪杰斯特拉算法应用举例如下图,使用迪杰斯特拉算法求下图的最短路径跌代过程:1)初始时从1开始寻找各节点到该节点的距离,路不通设置为maxint,此时把1归为s里面2)从1)得到距离1最短的路径对应的结点如上图为2,

大家好,又见面了,我是你们的朋友全栈君。如果您正在找激活码,请点击查看最新教程,关注关注公众号 “全栈程序员社区” 获取激活教程,可能之前旧版本教程已经失效.最新Idea2022.1教程亲测有效,一键激活。

Jetbrains全系列IDE使用 1年只要46元 售后保障 童叟无欺

如下图,使用迪杰斯特拉算法求下图的最短路径

实现迪杰斯特拉算法求某个源点到其余个点_迪杰斯特拉算法应用举例

 

实现迪杰斯特拉算法求某个源点到其余个点_迪杰斯特拉算法应用举例

跌代过程:

  

1) 初始时从1开始寻找各节点到该节点的距离,路不通设置为maxint,此时把1归为s里面

2)从1)得到距离1最短的路径对应的结点如上图为2,并把2归到s里面并求各节点(剩下的不在s里面的)到2的距离,如果新的距离更小的话则更新dist[i]

3) 从2)得到距离2最短的路径对应的结点如上图为4,并把4归到s里面并求各节点(剩下的不在s里面的)到4的距离,如果新的距离更小的话则更新dist[i]

4)依次类推可以把算有的节点遍历,并且最终的dist[i]便是从初始节点1到i的最短路径

算法如下

 1 #include<bits/stdc++.h>
 2 
 3 using namespace std;
 4 
 5 int main()
 6 {
 7     cout << "请输入图的顶点数" << endl;
 8     int n;
 9     cin >> n;
10     int Amap[n+1][n+1];
11     for(int i=1;i<=n;i++){//初始化map
12         for(int j=1;j<=n;j++){
13             Amap[i][j]=99999;
14         }
15     }
16     cout << " 请输入图的边数" << endl;
17     int m;
18     cin >> m;
19     cout << " 请输入图的边的起点和终点和边的长度" << endl;
20     int t1=0;
21     int t2=0;
22     int t3=0;
23     for(int j=0;j<m;j++){//更改t1到t2的长度
24         cin >> t1 >> t2 >> t3;
25         Amap[t1][t2]=t3;
26     }
27     int foot[n+1];//记录顶点是否归到已确定的路径里面
28     memset(foot,0,sizeof(foot));
29     foot[1]=1;//默认从1开始
30     int dist[n+1];//记录每个顶点所对应的最短特殊路径
31     for(int i=1;i<=n;i++){
32         dist[i]=Amap[1][i];//初始化第一个顶点的dist数组
33     }
34     int as[n];//用来记录经过的顶点顺序
35     memset(as,0,sizeof(as));
36     as[0]=1;//默认从一开始
37     int u;
38     for(int i=1;i<=n-1;i++){
39         int min=99999;
40         for(int j=1;j<=n;j++){//获取到该顶点的最短路径对应的下一个顶点的位置u
41             if(foot[j]==0 && dist[j]< min){
42                 min=dist[j];
43                 u=j;
44             }
45         }
46         foot[u]=1;//设置为一,表示已经选取
47         as[i]=u;//记录下来该顶点
48         for(int k=1;k<=n;k++){//更新当前的dist数组
49             if(Amap[u][k]<99999){//表示顶点之间有路径
50                 if(dist[k]>dist[u]+Amap[u][k]){//当前该顶点的dist不是最短的则更新
51                 dist[k] =dist[u] + Amap[u][k];
52             }
53             }
54         }
55 
56     }
57     cout << " 最短路径经过的顶点为"<<endl;
58     for(int i=0;i<n;i++){
59         cout <<  as[i] << " ";
60     }
61     cout << endl;
62     cout << "从一到各个顶点的长度为" << endl;
63     for(int i=1;i<=n;i++){
64     if(dist[i]==99999){
65         cout <<"从1到"<<i<< "的长度为"<<"-" << endl;
66         continue;
67     }
68         cout <<"从1到"<<i<< "的长度为"<<dist[i] << endl;
69     }
70     return 0;
71 }

运行结果截图为

实现迪杰斯特拉算法求某个源点到其余个点_迪杰斯特拉算法应用举例

 上述的代码并没有把从1到其它点的具体路径记录下来,下面是对上面的代码的升级,实现了路径的记录。

  1 #include<bits/stdc++.h>
  2 
  3 using namespace std;
  4 
  5 int main()
  6 {
  7     //freopen("D:/Data1.txt","r",stdin);
  8     cout << "请输入图的顶点数" << endl;
  9     int n;
 10     cin >> n;
 11     int road[n+1][n+1][n+1];//用来记录路径;
 12     memset(road,0,sizeof(road));
 13 
 14     int Amap[n+1][n+1];
 15     for(int i=1;i<=n;i++){//初始化map
 16         for(int j=1;j<=n;j++){
 17             Amap[i][j]=99999;
 18         }
 19     }
 20     cout << " 请输入图的边数" << endl;
 21     int m;
 22     cin >> m;
 23     cout << " 请输入图的边的起点和终点和边的长度" << endl;
 24     int t1=0;
 25     int t2=0;
 26     int t3=0;
 27     for(int j=0;j<m;j++){//更改t1到t2的长度
 28         cin >> t1 >> t2 >> t3;
 29         Amap[t1][t2]=t3;
 30     }
 31     for(int i=1;i<=1;i++){//初始化路线
 32         for(int j=1;j<=n;j++){
 33             for(int k=1;k<=2;k++){
 34                     if(k==1){
 35                         road[i][j][k]=1;
 36                     }
 37                   if(Amap[i][j]!=99999&&k==2){
 38                     road[i][j][k]=j;
 39                   }
 40             }
 41         }
 42     }
 43     int foot[n+1];//记录顶点是否归到已确定的路径里面
 44     memset(foot,0,sizeof(foot));
 45     foot[1]=1;//默认从1开始
 46     int dist[n+1];//记录每个顶点所对应的最短特殊路径
 47     for(int i=1;i<=n;i++){
 48         dist[i]=Amap[1][i];//初始化第一个顶点的dist数组
 49     }
 50     int as[n];//用来记录经过的顶点顺序
 51     memset(as,0,sizeof(as));
 52     as[0]=1;//默认从一开始
 53     int u;
 54     for(int i=1;i<=n-1;i++){
 55         int min=99999;
 56         for(int j=1;j<=n;j++){//获取到该顶点的最短路径对应的下一个顶点的位置u
 57             if(foot[j]==0 && dist[j]< min){
 58                 min=dist[j];
 59                 u=j;
 60             }
 61         }
 62         foot[u]=1;//设置为一,表示已经选取
 63         as[i]=u;//记录下来该顶点
 64         for(int k=1;k<=n;k++){//更新当前的dist数组
 65             if(Amap[u][k]<99999&&foot[k]==0){//表示顶点之间有路径
 66                 if(dist[k]>dist[u]+Amap[u][k]){//当前该顶点的dist不是最短的则更新
 67                 dist[k] =dist[u] + Amap[u][k];
 68                 for(int i1=1;i1<=n;i1++){//新的路径比原来的路径更短时更新并记录这个新的路径
 69                     if(road[1][u][i1]!=0){
 70                         road[1][k][i1]=road[1][u][i1];
 71                     }
 72                     else{
 73                         road[1][k][i1]=k;
 74                         break;
 75                     }
 76                 }
 77             }
 78             }
 79         }
 80 
 81     }
 82     cout << " 最短路径经过的顶点为"<<endl;
 83     for(int i=0;i<n;i++){
 84         cout <<  as[i] << " ";
 85     }
 86     cout << endl;
 87     cout << "从一到各个顶点的长度为" << endl;
 88     for(int i=1;i<=n;i++){
 89     if(dist[i]==99999){
 90         cout <<"从1到"<<i<< "的长度为"<<"-" << endl;
 91         continue;
 92     }
 93         cout <<"从1到"<<i<< "的长度为"<<dist[i] << endl;
 94          cout <<"从1到"<<i<< "的路径为:";
 95         for(int i1=1;i1<=n;i1++){
 96             if(road[1][i][i1]!=0){
 97                 cout << road[1][i][i1] <<"-->";
 98             }
 99         }
100         cout << "end" << endl;
101     }
102     return 0;
103 }

实现迪杰斯特拉算法求某个源点到其余个点_迪杰斯特拉算法应用举例

 

版权声明:本文内容由互联网用户自发贡献,该文观点仅代表作者本人。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。如发现本站有涉嫌侵权/违法违规的内容, 请发送邮件至 举报,一经查实,本站将立刻删除。

发布者:全栈程序员-用户IM,转载请注明出处:https://javaforall.cn/166693.html原文链接:https://javaforall.cn

【正版授权,激活自己账号】: Jetbrains全家桶Ide使用,1年售后保障,每天仅需1毛

【官方授权 正版激活】: 官方授权 正版激活 支持Jetbrains家族下所有IDE 使用个人JB账号...

(0)


相关推荐

  • PHP 安全问题入门:10 个常见安全问题 + 实例讲解

    PHP 安全问题入门:10 个常见安全问题 + 实例讲解

  • Dos攻击原理_防止xss攻击方法

    Dos攻击原理_防止xss攻击方法Technorati标签: DoS,攻击,网络防御,TCP,SYN_FloodTCP/IP协议的权限DoS(拒绝服务攻击)—–DenialofService该攻击的原理是利用TCP报文头来做的文章.下面是TCP数据段头格式。SourcePort和DestinationPort:是本地端口和目标端口SequenceNu

  • 五子棋人机对战思路「建议收藏」

    五子棋人机对战思路「建议收藏」五子棋人机对战:人机对战,我们可以想象一下我们在玩QQ游戏五子棋时的场景,根据每次下的步骤来分析电脑是怎样解析我们下棋的步骤的。下五子棋的步骤:1、第一步,黑子先下2、白子的第一步的最好的位置就是在黑子周围的八个点上3、接着黑子的第二步必然也是根据白子周围的八个点和自己的黑子所在的位置来下。4、如此循环下去。。。。那么对于计算机来说,就是让他找到第一个黑子周围的八个点,并且随机选中一个下白子。…

  • arraylist和linkedlist的区别_arraylist 和linkedlist

    arraylist和linkedlist的区别_arraylist 和linkedlist&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;这段时间把疯狂JAVA再看了一遍,发现Stack,ArrayDeque,LinkedList都可以作为栈使用,所以就稍微从性能以及实现的细节对比这三者的区别。类继承树&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;由继承树看出,三者都是Collection的间接实现类。&

  • 幼儿数学推理题图片_逻辑图形推理题

    幼儿数学推理题图片_逻辑图形推理题前天上幼儿园中班的侄子考了我一道题请在括号内填上正确的答案:(),(),2,4,6,7,8算了半小时都没头绪还被“羞辱”了一番:舅舅,这么简单的题都不会,还大学毕业的呢。看着侄子卖关子的表情,着实尴尬。✿赶✿紧✿想✿答✿案✿答案:(快来快来),(数一数),2,4,6,7,8!看完答案我感觉我的智商被侮辱了!气得我把我侄子“揍”了一顿如果你也没答出来千万别怀疑人生当今社会竞争那么激烈,仅仅拥有知…

  • java 获取当前系统时间 时间比较

    java 获取当前系统时间 时间比较JAVA获得当前时间的几种方法一.获取当前系统时间和日期并格式化输出:importjava.util.Date;importjava.text.SimpleDateFormat;publicclassNowString{publicstaticvoidmain(String[]args){ SimpleDateFormat

    2022年10月19日

发表回复

您的电子邮箱地址不会被公开。

关注全栈程序员社区公众号