Dijkstra 求最短路算法 ( 超级超级详细的 ) 不断更新中

输出样例：

3

题意很简单，在一个有向图中，求出 1 号结点到 n 号结点的最短距离，我们所举的第一个图示样例，就是这道题的数据。虽然是道模板题，但在具体实现过程中，会有很多小细节值得我们去留意和思考。

完整代码

#include<iostream>

#include<cstdio>

#include<algorithm>

#include<cstring>

using namespace std;

const int N=510;

int g[N][N]; //稠密图用邻接矩阵存储比较节省空间

int dist[N]; //dist[i] i 结点到起始点(1 号结点)的距离

bool st[N] ; //st[i] 用于标记 i 结点的最短路是否确定，若确定 st[i]=true;

int n,m;

int Dijkstra() //套用模板

{

memset(dist,0x3f,sizeof dist);//除 1 号结点外，其他均初始为无穷大

dist[

【一线大厂Java面试题解析+核心总结学习笔记+最新架构讲解视频+实战项目源码讲义】
浏览器打开：qq.cn.hn/FTf 免费领取

1]=0;

for(int i=0;i<n;i++) //n 次迭代，每次寻找不在 s 中距离最近的点 t

{

int t=-1;// 便于更新第一个点

for(int j=1;j<=n;j++)

if(!st[j]&&(t==-1||dist[j]<dist[t])) t=j;

st[t]=true; //将 t 加到 s 中

for(int j=1;j<=n;j++) //用 t 更新其他点的距离

dist[j]=min(dist[j],dist[t]+g[t][j]);

}

if(dist[n]==0x3f3f3f3f) return -1; //路径不存在

else return dist[n];

}

int main()

{

scanf("%d%d",&n,&m);

memset(g,0x3f,sizeof g); //邻接矩阵的初始化，由于求的是最小值，因此初始为无穷大

while(m--)

{

int x,y,z;

scanf("%d%d%d",&x,&y,&z);

g[x][y]=min(g[x][y],z); //重边中去取最小值

}

printf("%d\n",Dijkstra());

return 0;

}

如果有些地方不明白的话，不要着急，接着往下看

常见问题合集

1. 0x3f 为什么赋值的时候可以memset(dist,0x3f,sizeof dist)但是到后面验证的时候必须是if(dist[n]==0x3f3f3f3f)而不能是if(dist[n]==0x3f)
   

回答:：memset是按字节来初始化的，int 包含 4 个字节，所以初始化之后的值就是0x3f3f3f3f。

2. 为什么要用memset(dist,0x3f,sizeof dist)来初始化

回答:：0x3f3f3f3f 的十进制是 1061109567，是 1e9 级别的（和 0x7fffffff 一个数量级，0x7fffffff 代表了 32-bit int 的最大值），而一般场合下的数据都是小于 1e9 的，所以它可以作为无穷大使用而不致出现数据大于无穷大的情形。 另一方面，由于一般的数据都不会大于 10^9，所以当我们把无穷大加上一个数据时，它并不会溢出（这就满足了“无穷大加一个有穷的数依然是无穷大”），事实上0x3f3f3f3f+0x3f3f3f3f=2122219134，这非常大但却没有超过 32-bit int 的表示范围，所以0x3f3f3f3f还满足了我们“无穷大加无穷大还是无穷大”的需求。

3. for(int i=0;i<n;i++) { t=-1 } 这里为什么t要赋值为 -1
   

回答: 由于每一次都要找到还没有确定最短路距离的所有点中，距离当前的点最短的点。t = - 1是为了在st这个集合中找第一个点更新时候的方便所设定的。

4. 如果是问编号 a 到 b 的最短距离该怎么改呢? （好问题）

回答： 初始化时将 dist[a]=0,以及返回时return dist[b]。

5. 自环和重边对 Dijkstrea 算法有影响吗？

回答： 自环在朴素版 dijkstra 算法中是没有任何影响的，所以自环的权值是多少都可以，只要不是负数就行。而重边时，我们去取重边中的最小值 即代码g[x][y]=min(g[x][y],z)。

6. 为什么要用邻接矩阵去存贮，而不是邻接表？

回答： 我们采用邻接矩阵还是采用邻接表来表示图，需要判断一个图是稀疏图还是稠密图。稠密图指的是边的条数|E|接近于|V|2，稀疏图是指边的条数|E|远小于于|V|2（数量级差很多）。本题是稠密图，显然稠密图用邻接矩阵存储比较节省空间，反之用邻接表存储。

接下来讲讲堆优化版的 Dijkstra 算法

优化版 Dijkstra

实现过程

堆优化版的 dijkstra 是对朴素版 dijkstra 进行了优化，在朴素版 dijkstra 中时间复杂度最高的寻找距离最短的点 O(n^2)可以使用最小堆优化。

1. 一号点的距离初始化为零，其他点初始化成无穷大。

2. 将一号点放入堆中。

3. 不断循环，直到堆空。每一次循环中执行的操作为：

弹出堆顶（与朴素版 diijkstra 找到 S 外距离最短的点相同，并标记该点的最短路径已经确定）。

用该点更新临界点的距离，若更新成功就加入到堆中。

为了实现这个过程，我们首先要定义几个数组和函数。

int dist[N]; // 存储所有点到 1 号点的距离

bool st[N]; // 存储每个点的最短距离是否已确定

建立邻接表的函数（这里就不展开详讲了）

cost int N=1e5+10; //N 为边的数量

int h[N]; // h[i]存储编号为 i 结点的单链表的头结点的下标(地址)

int e[N]; // e[i]存储下标为 i 结点的编号

int ne[N]; // ne[i]存储下标为 i 结点所指向的下一个结点的下标(地址)

int idx; // idx 存储当前已经用到了哪个点

int w[N]

void add(int x,int y,int z) //编号为 a 和 b 的结点之间建立一条边,即 a 所对应的单链表中在头结点后插入 b

{

e[idx]=y,w[idx]=z,ne[idx]=h[x],h[x]=idx++;

}

定义一个优先队列来维护距离最近的点。

priority_queue<PII,vector<PII>,greater<PII>>heap

// first 存储距离，second 存储节点编号

接下来给出模板

时间复杂度 O(mlogn), n 表示点数，m 表示边数

typedef pair<int, int> PII;

int n; // 点的数量

int h[N], w[N], e[N], ne[N], idx; // 邻接表存储所有边

int dist[N]; // 存储所有点到 1 号点的距离

bool st[N]; // 存储每个点的最短距离是否已确定

// 求 1 号点到 n 号点的最短距离，如果不存在，则返回-1

int dijkstra()

{

memset(dist, 0x3f, sizeof dist);

dist[1] = 0;

priority_queue<PII, vector<PII>, greater<PII>> heap;

heap.push({0, 1}); // first 存储距离，second 存储节点编号

while (heap.size())

{

auto t = heap.top();

heap.pop();

int ver = t.second, distance = t.first;

if (st[ver]) continue;

st[ver] = true;

for (int i = h[ver]; i != -1; i = ne[i])

{

int j = e[i];

if (dist[j] > distance + w[i])

{

dist[j] = distance + w[i];

heap.push({dist[j], j});

}

}

}

if (dist[n] == 0x3f3f3f3f) return -1;

return dist[n];

}

看看这道模板题

AcWing 850. Dijkstra求最短路 II

给定一个 n 个点 m 条边的有向图，图中可能存在重边和自环，所有边权均为非负值。

请你求出 1 号点到 n 号点的最短距离，如果无法从 1 号点走到 n 号点，则输出-1。

输入格式

第一行包含整数 n 和 m。

接下来 m 行每行包含三个整数 x，y，z，表示存在一条从点 x 到点 y 的有向边，边长为 z。

输出格式

输出一个整数，表示 1 号点到 n 号点的最短距离。

如果路径不存在，则输出-1。

数据范围

1≤n,m≤1.5×105,

图中涉及边长均不小于 0，且不超过 10000。

输入样例：

3 3

1 2 2

2 3 1

1 3 4

输出样例：

3

这道题的数据范围相比上道题加强了很多，可以看出是个稀疏图，如果再用朴素版的 Dijkstra 算法,很容易超时，因此我们用优化版 Dijkstra 来实现。

完整代码

/*

朴素版 Dijkstras 算法适合于稠密图，时间复杂度为 O(n^2)

优化版 Dijkstras 算法适合于稀疏图，时间复杂度为 O(m*logn)

*/

#include<iostream>

#include<cstdio>

#include<queue>

#include<vector>

#include<cstring>

using namespace std;

typedef pair<int,int> PII;

const int N=1e6+10;

int e[N],ne[N],h[N],w[N],idx;

int dist[N];

int st[N];

int n,m;

void add(int x,int y,int z)

{

e[idx]=y,w[idx]=z,ne[idx]=h[x],h[x]=idx++;

}

int Dijkstra()

{

memset(dist,0x3f,sizeof dist);

dist[1]=0;

priority_queue<PII,vector<PII>,greater<PII>>heap;

heap.push({0,1});

while(heap.size())

{

PII t=heap.top(); //取出不在 s 中距离最短的点

heap.pop();

int ver=t.second,distance=t.first;

if(st[ver]) continue; //如果该点已经确定了最短距则跳过

st[ver]=true; //否则将该点加入 s 中

for(int i=h[ver];i!=-1;i=ne[i]) //用该点确定其他点的最短距离