dijkstra最短路算法

简介: dijkstra最短路算法

我们先看下题目描述:(这道题可以在acwing 上搜索 Dijkstra求最短路 I 来查看额原题额,顺便也把链接放这吧,就是不知道进不进得去,进不去就自己去acwing 上搜索。Dijkstra求最短路 I)

本着下面这个原则,最终成功拿下了!

while(有bug){
  改bug
  if(accept)break;
}

贴心时刻

担心各位老板测试时不想一个一个的输入,我特地把输入输出样例写了下来,各位老板直接复制即可!

输入样例:

3 3

1 2 2

2 3 1

1 3 4

输出样例:

3

同时,也担心各位老板难以滑动代码,我还特地的准备了图片版!

然后上源代码:

#include<bits/stdc++.h>
using namespace std;
#define maxn 510
//g数组存的是邻接矩阵,d数组存的是某点到起点的最短距离,
//st数组是用来装确定了的点(确定了到起点的距离最短的点)
int g[maxn][maxn],d[maxn],st[maxn];
int n,m;
int dijkstra(){
    memset(d,0x3f,sizeof(d));//先将所有距离设为最大
    d[1]=0;//起点到起点的距离为0
    for(int i=0;i<n;i++){//找出每个点到起点的距离,每次寻找不在st中距离最近的点t
        int t=-1;//用于更新第一个点,这个比较巧妙
        for(int j=1;j<=n;j++){//寻找不在st中,距离最近的点t
            if(!st[j]&&(t==-1||d[j]<d[t])) t=j;
        }
        st[t]=true;//将t加入到st中,表示已经确定了这个点
        for(int j=1;j<=n;j++){//通过t点来更新其它点的距离
            d[j]=min(d[j],d[t]+g[t][j]);
        }
    }
    d[n]!=0x3f3f3f3f?cout<<d[n]:cout<<-1;//输出答案
    return 0;
}
int main(){
    cin>>n>>m;
    memset(g,0x3f,sizeof(g));//因为是求的最小值,所以初始化为无穷大
    while(m--){
        int a,b,c;
        cin>>a>>b>>c;
        g[a][b]=min(g[a][b],c); //在重边中去取得最小值
    }
    dijkstra();//调用
    return 0;
}


相关文章
|
6月前
|
人工智能 算法 数据可视化
路径规划最全综述+代码+可视化绘图(Dijkstra算法+A*算法+RRT算法等)-2
路径规划最全综述+代码+可视化绘图(Dijkstra算法+A*算法+RRT算法等)-2
|
6月前
|
算法 Java C语言
第十四届蓝桥杯集训——练习解题阶段(无序阶段)-ALGO-5 算法训练 最短路
第十四届蓝桥杯集训——练习解题阶段(无序阶段)-ALGO-5 算法训练 最短路
37 0
|
17天前
|
存储 人工智能 算法
数据结构与算法细节篇之最短路径问题:Dijkstra和Floyd算法详细描述,java语言实现。
这篇文章详细介绍了Dijkstra和Floyd算法,这两种算法分别用于解决单源和多源最短路径问题,并且提供了Java语言的实现代码。
50 3
数据结构与算法细节篇之最短路径问题:Dijkstra和Floyd算法详细描述,java语言实现。
|
6月前
|
存储 人工智能 算法
路径规划最全综述+代码+可视化绘图(Dijkstra算法+A*算法+RRT算法等)-1
路径规划最全综述+代码+可视化绘图(Dijkstra算法+A*算法+RRT算法等)-1
|
27天前
|
存储 算法 程序员
迪杰斯特拉(Dijkstra)算法(C/C++)
迪杰斯特拉(Dijkstra)算法(C/C++)
|
3月前
|
机器学习/深度学习 算法 Java
算法设计(动态规划应用实验报告)实现基于贪婪技术思想的Prim算法、Dijkstra算法
这篇文章介绍了基于贪婪技术思想的Prim算法和Dijkstra算法,包括它们的伪代码描述、Java源代码实现、时间效率分析,并展示了算法的测试用例结果,使读者对贪婪技术及其应用有了更深入的理解。
算法设计(动态规划应用实验报告)实现基于贪婪技术思想的Prim算法、Dijkstra算法
|
3月前
|
算法
路径规划算法 - 求解最短路径 - Dijkstra(迪杰斯特拉)算法
路径规划算法 - 求解最短路径 - Dijkstra(迪杰斯特拉)算法
60 0
|
4月前
|
算法
基于Dijkstra算法的最优行驶路线搜索matlab仿真,以实际城市复杂路线为例进行测试
使用MATLAB2022a实现的Dijkstra算法在城市地图上搜索最优行驶路线的仿真。用户通过鼠标点击设定起点和终点,算法规划路径并显示长度。测试显示,尽管在某些复杂情况下计算路径可能与实际有偏差,但多数场景下Dijkstra算法能找到接近最短路径。核心代码包括图的显示、用户交互及Dijkstra算法实现。算法基于图论,不断更新未访问节点的最短路径。测试结果证明其在简单路线及多数复杂城市路况下表现良好,但在交通拥堵等特殊情况下需结合其他数据提升准确性。
|
4月前
|
资源调度 算法 定位技术
|
4月前
|
算法 Java C++
《经典图论算法》迪杰斯特拉算法(Dijkstra)
这个是求最短路径的迪杰斯特拉算法,另外我还写了50多种《经典图论算法》,每种都使用C++和Java两种语言实现,熟练掌握之后无论是参加蓝桥杯,信奥赛,还是其他比赛,或者是面试,都能轻松应对。