接下来给出模板

朴素版dijkstra算法

时间复杂是 O(n^2+m), n 表示点数，m 表示边数

int g[N][N]; // 存储每条边

int dist[N]; // 存储1号点到每个点的最短距离

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

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

int dijkstra()

{

memset(dist, 0x3f, sizeof dist);

dist[1] = 0;

for (int i = 0; i < n - 1; i ++ )

{

int t = -1; // 在还未确定最短路的点中，寻找距离最小的点

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

if (!st[j] && (t ==

《一线大厂Java面试题解析+后端开发学习笔记+最新架构讲解视频+实战项目源码讲义》

【docs.qq.com/doc/DSmxTbFJ1cmN1R2dB】 完整内容开源分享

-1 || dist[t] > dist[j]))

t = j;

// 用t更新其他点的距离

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

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

st[t] = true;

}

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

return dist[n];

}

好了接下来我们来看一道模板题，实践是检验真理的唯一标准

AcWing 849. Dijkstra求最短路 I

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

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

输入格式

第一行包含整数n和m。

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

输出格式

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

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

数据范围

1≤n≤500,

1≤m≤105,

图中涉及边长均不超过10000。

输入样例：

3 3

1 2 2

2 3 1

1 3 4

输出样例：

3

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

完整代码

#include

#include

#include

#include

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[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|²，稀疏图是指边的条数|E|远小于于|V|²（数量级差很多）。本题是稠密图，显然稠密图用邻接矩阵存储比较节省空间，反之用邻接表存储。

接下来讲讲堆优化版的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,greater>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, greater> 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。