| Dijkstra求最短路 I（Dijkstra算法） | 您所在的位置：网站首页 › dijkstra算法求最短路例题 › Dijkstra求最短路 I（Dijkstra算法） |
Dijkstra求最短路 I（Dijkstra算法）
|
给定一个 n 个点 m 条边的有向图，图中可能存在重边和自环，所有边权均为正值。 请你求出 1 号点到 n 号点的最短距离，如果无法从 1 号点走到 n 号点，则输出 −1。 输入格式第一行包含整数 n 和 m。 接下来 m 行每行包含三个整数 x,y,z，表示存在一条从点 x 到点 y 的有向边，边长为 z。 输出格式输出一个整数，表示 1 号点到 n 号点的最短距离。 如果路径不存在，则输出 −1。 数据范围1≤n≤500, 1≤m≤10^5, 图中涉及边长均不超过10000。 输入样例： 3 3 1 2 2 2 3 1 1 3 4 输出样例： 3思路： 最短路问题，可以用dijkstra算法来解决，这里是解决各种最短路问题的框架
因为这道题求的是单源最短路，且每条路权值都为正数，并且边的量级明显大于点（1≤n≤500, 1≤m≤10^5），是稠密图，所以用朴素dijkstra算法解决 朴素dijkstra算法的原理：
初始化，除了起点之外，每个点到起点的距离为无穷大。我们创建一个集合s，表示当前已确定最短距离的点，对于n个点，循环n次，每次找到一个不在集合s中的离起点（题目中的1号点）最近的点，然后将它加入集合s，并用这个点去更新其他所有点距离。 const int N=510; int n,m; int g[N][N]; //题目中是稠密图，用邻接矩阵写，g[1][2]表示从1节点指向2节点的距离 int dist[N]; //从1号点走到每个点的距离（最短距离） bool st[N]; //每个点最短路是否已经确定,true为确定因为是稠密图，所以我们用邻接矩阵g[ ][ ]存储边和点的关系。 for(int i=0;ia>>b>>c; g[a][b]=min(g[a][b],c); //如果两个点之间有多条边，保留最短边，因为初始化g为无穷大，所以一开始是让g[a][b]=c，后面如果出现了一样的点，就会取其中的最小值 }在主函数中，因为题目没有说不存在自边和环，所以可能从一个点到另一个点有多条边，我们只需要保留其中最短的就好。 补充：这里的代码很多处都用到了0x3f，是因为这个数字能近似表达正无穷，它的值是1061109567，是10^9级别，并且还能保证无穷大加无穷大仍然不会超限，因为0x3f3f3f3f+0x3f3f3f3f=2122219134，这非常大但却没有超过32-bit int的表示范围，我们使用memset()是对char操作，即一个字节一个字节的操作，如果此时初始化的变量为int类型（4字节），那么此时的变量就会被初始化成四个0x3f，即0x3f3f3f3f（这个0x是十六进制的意思）。 if(dist[n] == 0x3f3f3f3f) //当1号点距离到n号点距离为无穷大时（即1和n不连通），注意这里变成了0x3f3f3f3f { return -1; }在后面比较的时候，注意这个值是0x3f3f3f3f，我们只是用memset赋值的时候给每个字节赋值0x3f，整个int变量是0x3f3f3f3f。 参考：0x3f~0x3f3f3f3f的来龙去脉（详解）-CSDN博客关于memset函数和赋值0x3f，2021-5-5-CSDN博客 示例代码： #include #include #include using namespace std; const int N=510; int n,m; int g[N][N]; //题目中是稠密图，用邻接矩阵写，g[1][2]表示从1节点指向2节点的距离 int dist[N]; //从1号点走到每个点的距离（最短距离） bool st[N]; //每个点最短路是否已经确定,true为确定 int dijkstra() { memset(dist,0x3f,sizeof(dist)); //初始化时每个点到起点距离为无穷大 dist[1]=0; //起点到自身的距离为0 for(int i=0;in>>m; //读入点数和边数 memset(g,0x3f,sizeof(g)); //0x3f是无穷大，memset按字节赋值，一个字节就是0x3f，int有四个字节，所以是0x3f3f3f3f while(m--) { int a,b,c; cin>>a>>b>>c; g[a][b]=min(g[a][b],c); //如果两个点之间有多条边，保留最短边，因为初始化g为无穷大，所以一开始是让g[a][b]=c，后面如果出现了一样的点，就会取其中的最小值 } cout |
【本文地址】