Dijkstra求最短路
最短路问题
朴素版本的 Dijkstra算法
Dijkstra算法
迪杰斯特拉算法(Dijkstra)是由荷兰计算机科学家狄克斯特拉于1959 年提出的,因此又叫狄克斯特拉算法。是从一个顶点到其余各顶点的最短路径算法,解决的是有权图中最短路径问题。迪杰斯特拉算法主要特点是从起始点开始,采用贪心算法的策略,每次遍历到始点距离最近且未访问过的顶点的邻接节点,直到扩展到终点为止。
我们先看看从1号点到n号点的最短距离怎么求。
实现过程
代码
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];
}
完整代码
#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[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;
}
如果有些地方不明白的话,不要着急,接着往下看.
常见问题合集
- 0x3f为什么赋值的时候可以
memset(dist,0x3f,sizeof dist)
但是到后面验证的时候必须是if(dist[n]==0x3f3f3f3f)
而不能是if(dist[n]==0x3f)
回答::memset
是按字节来初始化的,int包含4个字节,所以初始化之后的值就是0x3f3f3f3f
。 - 为什么要用
memset(dist,0x3f,sizeof dist)
来初始化
回答::0x3f3f3f3f的十进制是1061109567,是1e9级别的(和0x7fffffff一个数量级,0x7fffffff代表了32-bit int的最大值),而一般场合下的数据都是小于1e9的,所以它可以作为无穷大使用而不致出现数据大于无穷大的情形。 另一方面,由于一般的数据都不会大于10^9,所以当我们把无穷大加上一个数据时,它并不会溢出(这就满足了“无穷大加一个有穷的数依然是无穷大”),事实上0x3f3f3f3f+0x3f3f3f3f=2122219134
,这非常大但却没有超过32-bit int的表示范围,所以0x3f3f3f3f
还满足了我们“无穷大加无穷大还是无穷大”的需求。 for(int i=0;i<n;i++) { t=-1 }
这里为什么t
要赋值为-1
回答: 由于每一次都要找到还没有确定最短路距离的所有点中,距离当前的点最短的点。t = - 1
是为了在st
这个集合中找第一个点更新时候的方便所设定的。- 如果是问编号a到b的最短距离该怎么改呢? (好问题)
回答: 初始化时将dist[a]=0
,以及返回时return dist[b]
。 - 自环和重边对 Dijkstrea算法有影响吗?
回答: 自环在朴素版dijkstra算法中是没有任何影响的,所以自环的权值是多少都可以,只要不是负数就行。而重边时,我们去取重边中的最小值 即代码g[x][y]=min(g[x][y],z)
。 - 为什么要用邻接矩阵去存贮,而不是邻接表?
回答: 我们采用邻接矩阵还是采用邻接表来表示图,需要判断一个图是稀疏图还是稠密图。稠密图指的是边的条数|E|接近于|V|²,稀疏图是指边的条数|E|远小于于|V|²(数量级差很多)。本题是稠密图,显然稠密图用邻接矩阵存储比较节省空间,反之用邻接表存储。
问题会持续更新,欢迎评论区留言。
t = -1的理解:进来for( i )这一时刻,(计算机)不知道跟谁 ” 可以 ” 是最短的,因为还没懂state[j]的状态。俗的讲:不能确定t(表示节点)的具体值,所以就索性用其他的值表示(除了节点值之外,可以等于0,-1,-10,100都行)未定。等获得足够的信息,既符合state[j] 、 d[] 后, 才开始更新
现在我好像知道是怎么回事了,首先dist[-1]=0。如果他是没有下一个点和它联通的话,那么他会找到从i~n中第一个没有确定最短距离的点j,令t=j,那么此时的dist[t]=0x3f3f3f3f,那么他也就不会更新其他点了,并且这个点已经被标记过了。那么下一个也就不会找到这个点了,那么这里是t=-1的作用可能就是使得每一个点都会被标记。
在更新其他点距离的时候,我怎么知道起点能不能走到该点呢
为什么
st[1] = true
为啥不先这样呢,这个1为啥不进入st呢这个怎么理解
t = -1的理解:进来for( i )这一时刻,(计算机)不知道跟谁 ” 可以 ” 是最短的,因为还没懂state[j]的状态。俗的讲:不能确定t(表示节点)的具体值,所以就索性用其他的值表示(除了节点值之外,可以等于0,-1,-10,100都行)未定。等获得足够的信息,既符合state[j] 、 d[] 后, 才开始更新
现在理解了吗佬,t=j是啥意思
离当前集合的最近的一个点
%%%
牛!
讲的非常好!
n次迭代,每次寻找不在s中距离最近的点t
为啥迭代n次
因为有n个点,每次迭代确定一个点的最小距离
为什么每次迭代能确定一个点的最小距离
那个t刚开始为啥得赋值为-1
赋值为负值,便于更新第一个点。
tqltqltql
nbnb!
赞
写的很好!
谢谢hh!
有木有堆优化的
思维脑图赞~ 问题情形分类nice i了i了
hh,谢谢
唉你是帝国的么
我们学校的江湖绰号,23333