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

2021/12/26 12:07:08

本文主要是介绍Dijkstra求最短路算法 ( 超级超级详细的 ) 不断更新中,对大家解决编程问题具有一定的参考价值,需要的程序猿们随着小编来一起学习吧!

接下来给出模板

朴素版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

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

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

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

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

  1. 如果是问编号a到b的最短距离该怎么改呢? (好问题)

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

  1. 自环和重边对 Dijkstrea算法有影响吗?

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

  1. 为什么要用邻接矩阵去存贮,而不是邻接表?

回答: 我们采用邻接矩阵还是采用邻接表来表示图,需要判断一个图是稀疏图还是稠密图。稠密图指的是边的条数|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。



这篇关于Dijkstra求最短路算法 ( 超级超级详细的 ) 不断更新中的文章就介绍到这儿,希望我们推荐的文章对大家有所帮助,也希望大家多多支持为之网!


扫一扫关注最新编程教程