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

实现迪杰斯特拉算法求某个源点到其余个点_迪杰斯特拉算法应用举例如下图,使用迪杰斯特拉算法求下图的最短路径跌代过程: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)
blank

相关推荐

  • spring cloud熔断器原理_a股熔断机制是什么时候

    spring cloud熔断器原理_a股熔断机制是什么时候1.熔断机制介绍在介绍熔断机制之前,我们需要了解微服务的雪崩效应。在微服务架构中,微服务是完成一个单一的业务功能,这样做的好处是可以做到解耦,每个微服务可以独立演进。但是,一个应用可能会有多个微服务组成,微服务之间的数据交互通过远程过程调用完成。这就带来一个问题,假设微服务A调用微服务B和微服务C,微服务B和微服务C又调用其它的微服务,这就是所谓的“扇出”。如果扇出的链路上某个微服务的调用响应时…

    2022年10月31日
  • java获取当前日期等以及时区

    java获取当前日期等以及时区

  • pip更新方法

    pip更新方法pip更新方法如下:方法一:pycharm中的Terminal中更新,使用如下命令:python-mpipinstall–upgradepip方法二:删除原pip文件,重新安装例如pip文件在如下文件夹中C:\Python\Python373\Lib\site-packages我们能够知道pip20.1.1所在路径,找到它,然后删掉pip-20.1.1.dist-info文件夹。设置如下图,已不见pip的踪影。提示,packagi…

  • linux的gcc使用方法_linux怎么用gcc编译

    linux的gcc使用方法_linux怎么用gcc编译01.命令概述gcc命令使用GNU推出的基于C/C++的编译器,是开放源代码领域应用最广泛的编译器,具有功能强大,编译代码支持性能优化等特点。gcc是GNU编译器套件(GNUCompilerCollection),它包括了C、C++、Objective-C、Fortran、Java、Ada、Go语言和D语言的前端,也包括了这些语言的库(如libstdc++、libgcj等等)。GCC的初衷是…

    2022年10月13日
  • python中多个if语句用法_if语句的用法

    python中多个if语句用法_if语句的用法python中if语句用法以下实例通过使用if…elif…else语句判断数字是正数、负数或零:推荐:《python教程》实例(Python3.0+)#Filename:test.py#authorby:www.php.cn#用户输入数字num=float(input(“输入一个数字:”))ifnum>0:print(“正数”)elifnum==…

  • Ubuntu终端打开文件及查看目录「建议收藏」

    Ubuntu终端打开文件及查看目录「建议收藏」方法/步骤 1ctrl+alt+t,调出终端。———— 要去某个目录,用cd 例如:cd/home/yang/下载/ 在视图中,后面还有一个文件夹,我记不住,就按tab键一下。就自动出来了。 如果该文件夹下东西比较多,你记不住,那就多按两次tab,就会出现可以进入的文件夹。在这里我要进入【下载】文件夹里。————- …

    2022年10月11日

发表回复

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

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