有之前宽搜和深搜的基础 再听了y总的课 就感觉思路特别清晰了
最近复习了下Dijkstra 发现之前的理解还是有些不太到位
所以更新了一下 希望能帮助一起学算法的小伙伴理清思路
Dijkstra 的整体思路比较清晰
即进行n（n为n的个数）次迭代去确定每个点到起点的最小值 最后输出的终点的即为我们要找的最短路的距离
所以按照这个思路除了存储图外我们还需要存储两个量
dist[n] //用于存储每个点到起点的最短距离
st[n] //用于在更新最短距离时 判断当前的点的最短距离是否确定 是否需要更新
每次迭代的过程中我们都先找到当前未确定的最短距离的点中距离最短的点
（至于为什么是这样那么这就涉及到Dijkstra算法的具体数学证明了 有兴趣的同学可以百度一下）
int t=-1; //将t设置为-1 因为Dijkstra算法适用于不存在负权边的图
for(int j=1;j<=n;j++)
{
if(!st[j]&&(t==-1||dist[t]>dist[j]) //该步骤即寻找还未确定最短路的点中路径最短的点
t=j;
}
通过上述操作当前我们的t代表就是剩余未确定最短路的点中 路径最短的点
而与此同时该点的最短路径也已经确定我们将该点标记
st[t]=true;
然后用这个去更新其余未确定点的最短距离
for(int j=1;j<=n;j++)
dist[j]=min(dist[j],dist[t]+g[t][j]);
//这里可能有同学要问j如果从1开始的话 会不会影响之前已经确定的点的最小距离
//但其实是不会 因为按照我们的Dijkstra算法的操作顺序 先确定最短距离的点的距离已经比后确定的要小 所以不会影响
//当然你也可以在循环判断条件里加上if(!st[i])
//这里j从1开始只是为了代码的简洁
进行n次迭代后最后就可以确定每个点的最短距离
然后再根据题意输出相应的 要求的最短距离
以下为完整代码
#include<iostream>
#include<algorithm>
#include<cstring>
using namespace std;
const int N=510;
int g[N][N]; //为稠密阵所以用邻接矩阵存储
int dist[N]; //用于记录每一个点距离第一个点的距离
bool st[N]; //用于记录该点的最短距离是否已经确定
int n,m;
int Dijkstra()
{
memset(dist, 0x3f,sizeof dist); //初始化距离 0x3f代表无限大
dist[1]=0; //第一个点到自身的距离为0
for(int i=0;i<n;i++) //有n个点所以要进行n次 迭代
{
int t=-1; //t存储当前访问的点
for(int j=1;j<=n;j++) //这里的j代表的是从1号点开始
if(!st[j]&&(t==-1||dist[t]>dist[j]))
t=j;
st[t]=true;
for(int j=1;j<=n;j++) //依次更新每个点所到相邻的点路径值
dist[j]=min(dist[j],dist[t]+g[t][j]);
}
if(dist[n]==0x3f3f3f3f) return -1; //如果第n个点路径为无穷大即不存在最低路径
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()<<endl;
return 0;
}
有hxd不懂，聊天框里发他后格式太乱所以就扔这里了
①解释：
堆中定义：dist[t]存点n到点1的“距离”（注意dist[t]一直在用min修改，直到对应state[t]置为true才是距离点1的最短距离）；st[t]存true/false，或者0/1也行，用于判断是否已经确定这个点为最短路径上的点，或者dist[t]是否为最短距离，一个意思；g[t] [j]里存的是图中相邻两点t到j的距离（因为有向图用邻接矩阵嘛）
前提：现在假设最外层循环到i=k(1<k<n-1)了哈，就是最短路径上已经有k个点了，按执行顺序去理解
int t=-1;t存储当前状态下（最短路径还没生成完嘛）下一次访问的点。t==-1/0都行,只要保证dist[t]=INF就可for(int j=1;j<=n;j++) if(!st[j]&&(t==-1||dist[t]>dist[j])) t=j;这三行是找当前状态下，下一次访问的点，即dist[]最小的点。很明显嘛，!state先除掉到已经确定的距离起点是最短距离的点（就是在当前已确定的最短路径上的点），后面都是state=false的点了吧，然后&&(t==-1||dist[t]>dist[j])，执行一下t=j开始找下一个点了，后面只要dist[t]>dist[j]就令t=j，就是一直在找dist[]最小的那个点嘛.然后
st[t]=true; 就是确定这个点就是当前最短路径的下一个点了。执行
dist[j]=min(dist[j],dist[t]+g[t][j])；对于点t之前的那些已经确定在最短路径上的点，因为最短路径中这些点都在点t前面，所以min(dist[j],dist[t]+g[t][j])直接就是dist[j]嘛不变。对于点t之后的，就是更新到点t相邻的点的路径值，这些更新后的dist[]用于下一次i=k+1循环中找接下来哪个点距离起点最短。
然后循环到n-1次完事，每次就是贪心。
②还没弄懂的话：
1）减一找个有图解的题解，走一遍（推荐第二个题解，例子是个不带重边和自环的简单图，可以看看。
2）然后再花十来分钟自己把代码走一遍就懂了：）
…码了好多字赞
爆赞
众口交赞、有赞有弹、赞叹不已.....在你这我看懂啦啦啦!
dist[t] = INF 这个INF啥意思啊
无穷大
dalao，我觉得st应该不是是否确定最短距离，我觉得应该是是否以i点为更新点，更新过其他点，因为一开始在dijkstra里面dist[1]=0，那么1这个点已经被确定了最短距离，如果按照你文章上的理解，那么st[1]可以直接变为true，但是如果直接在dist[1]=0后面加上st[1]=true，答案就会出错，因为无法从1这个点来更新别的点，而且从y总的讲课上，也可以看出来st[i]的含义应该是：是否以i这个点更新过其他点
说得好
从逻辑上讲dist只是记录每一个点到第一个点的距离 并不代表最短距离 事实上在后面的迭代过程中dist的值是一直在变的
以1这个点的情况为例
事实上是下面这段代码才确定了当前距离最短的点是1点
for(int j=1;j<=n;j++)
if(!st[j]&&(t==-1||dist[t]>dist[j]))
t=j;
而当确定了这个最短距离点后才dist[j]=min(dist[j],dist[t]+g[t][j]);
也就是说st[1]=true时 还并没有这个点更新过其他点
dist[1]=0 我觉得更多的是可以理解为是像一些DP问题里面的边界情况
悟了
st就是 是否已经确定最短距离,你不能直接在dist[1]=0后面加上st[1]=true，因为dist[1]应该在循环完了之后才能被确定为到起点的距离最短，因此不能在后面直接变成true， 而且你的理由和st的含义没啥关系，你的理由 “因为无法从1这个点来更新别的点” 这句话是由代码决定的，你先让st[1] = true; 在接下来的的for循环中if永远为假，当然无法更新其他点了。
在更新距离的时候，加上if(!st[j]) 也能过，说明更新的是还没有确定最短距离的点
说的很有道理
for(int j=1;j<=n;j++) //依次更新每个点所到相邻的点路径值
dist[j]=min(dist[j],dist[t]+g[t][j]);
}
为啥要到n ， 不是到相邻的点吗
j从1到n就是为了更新t相邻的点，与t不相邻的点的g[t][j]的值为无限大，不会被更新。这样从1到n的与t相邻的点不会被遗漏，保证了与t相连的点都能被更新
与t不相邻的点g[t][j]就是不存在边，所以为无限大
是这样的
补充一下Dijkstra算法正确性证明
https://www.acwing.com/file_system/file/content/whole/index/content/7317949/
请问t==-1是什么作用？题目给的结点编号是1~n，把t改成0代码也可以ac，难道t是为了找第一个点
存储距离未被确定的距离最小点的编号，0和-1是等价的，因为编号是从1开始的。
就是个没卵用的赋值。
是个标记
dist[t] 等于多少啊？ 0x3f吗？还是
0x3f3f3f3f
相加的时候会不会溢出
数据范围表示不会
溢出
if(!s[j]&&(t==-1||dist[t]>dist[j]))中(t==-1||dist[t]>dist[j])请问一下是什么意思
j为还没确定最短路径的点同时t还没有指向为第一次成立
接着下面成立就是j为还未确定最短路径的点同时t所指向的点的最短距离比j长，就是第二次成立
最后下来t就是未确定最短路径的点的集合中距离起点最短的点
t = -1的理解：进来for( i )这一时刻，（计算机）不知道跟谁 ” 可以 ” 是最短的，因为还没懂state[j]的状态。俗的讲：不能确定t（表示节点）的具体值，所以就索性用其他的值表示（除了节点值之外，可以等于0，-1，-10，100都行）未定。等获得足够的信息，既符合state[j] 、 d[] 后, 才开始更新
嘻嘻写得不错
保存的是x到y的最短的距离
应该是迭代n-1次吧，dist[1]=0刚开始已经初始化了（第一个点已经确定了，后面还剩下n-1个点，只需要迭代n-1次）
复杂度太高了，只能适合这题，数据量小
堆优化版Dijkstra不能处理边数多的图，这题可以处理点数少的图
可以把t赋值成0。因为初始d数组的时候d[0]==0x3f3f3f3f,第一次可以进循环
$%%%$
我一直在想怎么解释这句话：
1. 对 x 点来说，最短路径是指起点到x的最短距离
2. 现在， 有许多你无法分辨是否是最短距离的点
3. 所以， 你需要在这些点之中， 找到一个距离起点最近的点
4. 原因是， 距离起点最近的点可能会减少其余点的最短距离， 而距离起点远的点则一定不会减少其余点的最短距离
#### 更正
4. 而距离起点远的点则一定不会减少距离起点最近的点的距离
而这也是dijkstra无法解决存在负权路径的原因：由于存在负权，距离起点远的点则一定不会减少距离起点最近的点的最短距离就不成立了
说得好！！orz
写得好orz
memset（g）是为了防止重边吧，因为如果不初始化0x3f的话，下面的min操作一直会取零（因为这个算法不能解决负权），换句话说memset(g)和min(g,z)是匹配的操作
谢谢，听懂了，写的很棒哦！
写得好呀！！
#l厉害