Dijkstra朴素算法
思路:
进行n次迭代确定n个点到起点的最短距离,之后输出终点到起点的最短距离。
1.首先我们需要先定义几个数组来存储图和相关的量:
int g[N][N]; //g[i][j]表示从i到j的边的权重
int dist[N]; //dist[i]表示i点到起点的距离
bool st[N]; //st[i]表示i点到起点的距离是否已经确定
2.然后需要对相关量进行初始化
memset(dist, 0x3f, sizeof dist); //将所有点到起点的距离初始化为无穷大
dist[1]=0; //第一个点(即起点)到起点的距离是0
3.接下来就是n次迭代:
①先定义点t,代表我们需要查找的点
int t=-1;//t就是我们需要找到的点,-1表示还没有开始寻找
②先从n个点中找到剩余未确定最短路的点中,离起点最近的点(即dist[]最小的点)
for(int j=1;j<=n;j++)
{ //需要更新t的情况:
if(!st[j]&&(t==-1||dist[t]>dist[j]))//①t点的最短路还未确定②t未开始查找或者当前点的dist小于之前查找的t的dist
t=j;
}
③此时的t点就是我们需要找的点:剩余未确定最短路的点中,离起点最近的点。将其状态设置为已经确定
st[t]=ture;
④用t点去更新其余的点到起点的最短距离
for(int j=1;j<=n;j++)
{
if(!st[j])//此步其实是没有必要的
dist[j]=min(dist[j],dist[t]+g[t][j]);
}
因为按照我们的Dijkstra算法的操作顺序,先确定最短距离的点的距离已经比后确定的要小,所以不会影响。
4.进行n次迭代后最后就可以确定每个点的最短距离,然后再根据题意输出相应的要求的最短距离
代码:
#include <iostream>
#include <cstring>
#include <algorithm>
using namespace std;
const int N = 510;
int g[N][N]; //g[i][j]表示从i到j的边的权重,因为是稠密图所以用邻接矩阵
int dist[N]; //dist[i]表示i点到起点的距离
bool st[N]; //st[i]表示i点到起点的距离是否已经确定
int n, m;
int Dijkstra()
{
memset(dist, 0x3f, sizeof dist); //将所有点到起点的距离初始化为无穷大
dist[1] = 0; //第一个点(即起点)到起点的距离是0
for (int i = 1; i <= n; i++)
{
int t = -1;//t就是我们需要找到的点,-1表示还没有开始寻找
for (int j = 1; j <= n; j++)//先从n个点中找到剩余未确定最短路的点中,离起点最近的点
{
if (!st[j] && (t == -1 || dist[t] > dist[j]))
t = j;
}
st[t] = true;
for (int j = 1; j <= n; j++)//用t点去更新其余的点到起点的最短距离
{
dist[j] = min(dist[j], dist[t] + g[t][j]);
}
}
if (dist[n] == 0x3f3f3f3f)
return -1; //如果第n个点路径为无穷大即不存在最低路径
else
return dist[n];
}
int main()
{
cin >> n >> m;
memset(g, 0x3f, sizeof g);
while (m--)
{
int x, y, z;
cin >> x >> y >> z;
g[x][y] = min(g[x][y], z); //如果发生重边的情况则保留最短的一条边
}
cout << Dijkstra();
return 0;
}
大佬,我有一个疑问:在朴素版 Dijkstra 算法中,$n$ 次迭代的时候每次循环都会执行一遍
int t = -1
,那第一步:”找到当前未标记过且离源点最近的点“ 这个循环的过程中,if
条件的!st[j] && (t == -1 || dist[j] < dist[t])
,那只用写t = -1
就可以了呀,为什么还要写dist[j] < dist[t]
?因为我们要在所有未被标记过的点中找到里源点最近的点,假如我们找到了第一个未被标记的点j==3 , 那么t从-1更新为3,但是3号点之后的未标记过的点中可能存在离起点更近的点,例如我们设d[3]=6,当j==4且st[j]==0时,这时候的d[j]==5,那么此时4号点离源点的距离就比3号点更近,因此我们要将t更新为4
懂了,谢谢大佬