[Acwing算法基础] 3.4 Dijkstra算法
2021/5/23 12:28:47
本文主要是介绍[Acwing算法基础] 3.4 Dijkstra算法,对大家解决编程问题具有一定的参考价值,需要的程序猿们随着小编来一起学习吧!
Dijkstra算法使用于单源最短路且不存在负权边的问题。时间复杂度为O(n^2)。
Dijkstra算法的时间复杂度与图的边无关,所以适合于稠密图
本文以Acwing 849. Dijkstra求最短路I作为例子对Dijkstra算法进行说明
算法思想
Dijkstra 的整体思路比较清晰
即进行n(n为n的个数)次迭代去确定每个点到起点的最小值 最后输出的终点的即为我们要找的最短路的距离
所以按照这个思路除了存储图外我们还需要存储两个量
1. 图的邻接矩阵存储
图的稠密图的保存使用一个二维数组保存。图的构建和保存的代码如下:
int g[N][N]; //为稠密阵所以用邻接矩阵存储 cin>>n>>m; while(m--) { int x,y,z; cin>>x>>y>>z; g[x][y]=min(g[x][y],z); //如果发生重边的情况则保留最短的一条边 }
2. 找到剩余未确定的点中路径最短的点
为啥是这样等我的算法导论到了再看看吧
int t=-1; //将t设置为-1 因为Dijkstra算法适用于不存在负权边的图 for(int j=1;j<=n;j++) { if(!st[j]&&(t==-1||dist[t]>dist[j]) //该步骤即寻找还未确定最短路的点中路径最短的点 t=j; }
将该点标记为距离已确定
st[j] = true;
3. 使用刚刚找到的t更新其余未确定点的最短距离
这里j从1开始遍历是为了使代码更简洁,而且并不会改变已经确定的距离。
for(int j=1;j<=n;j++) dist[j]=min(dist[j],dist[t]+g[t][j]);
以上就是代码模板的主体部分。
完整代码
#include<iostream> #include<algorithm> #include<cstring> using namespace std; const int N=510; int g[N][N]; //为稠密阵所以用邻接矩阵存储 int dist[N]; //用于记录每一个点距离第一个点的距离 bool st[N]; //用于记录该点的最短距离是否已经确定 int n,m; int Dijkstra() { memset(dist, 0x3f,sizeof dist); //初始化距离 0x3f代表无限大 dist[1]=0; //第一个点到自身的距离为0 for(int i=0;i<n;i++) //有n个点所以要进行n次 迭代 { int t=-1; //t存储当前访问的点 for(int j=1;j<=n;j++) //这里的j代表的是从1号点开始 if(!st[j]&&(t==-1||dist[t]>dist[j])) t=j; st[t]=true; for(int j=1;j<=n;j++) //依次更新每个点所到相邻的点路径值 dist[j]=min(dist[j],dist[t]+g[t][j]); } if(dist[n]==0x3f3f3f3f) return -1; //如果第n个点路径为无穷大即不存在最低路径 return dist[n]; } int main() { cin>>n>>m; memset(g,0x3f,sizeof g); //初始化图 因为是求最短路径 //所以每个点初始为无限大 while(m--) { int x,y,z; cin>>x>>y>>z; g[x][y]=min(g[x][y],z); //如果发生重边的情况则保留最短的一条边 } cout<<Dijkstra()<<endl; return 0; }
这篇关于[Acwing算法基础] 3.4 Dijkstra算法的文章就介绍到这儿,希望我们推荐的文章对大家有所帮助,也希望大家多多支持为之网!
- 2024-05-15PingCAP 黄东旭参与 CCF 秀湖会议,共探开源教育未来
- 2024-05-13PingCAP 戴涛:构建面向未来的金融核心系统
- 2024-05-09flutter3.x_macos桌面os实战
- 2024-05-09Rust中的并发性:Sync 和 Send Traits
- 2024-05-08使用Ollama和OpenWebUI在CPU上玩转Meta Llama3-8B
- 2024-05-08完工标准(DoD)与验收条件(AC)究竟有什么不同?
- 2024-05-084万 star 的 NocoDB 在 sealos 上一键起,轻松把数据库编程智能表格
- 2024-05-08Mac 版Stable Diffusion WebUI的安装
- 2024-05-08解锁CodeGeeX智能问答中3项独有的隐藏技能
- 2024-05-08RAG算法优化+新增代码仓库支持,CodeGeeX的@repo功能效果提升