为了使得整篇文章显得更加人性化，咱们首先说一下最短路。
声明：不是讲解知识点不是讲解知识点不是讲解知识点不是讲解知识点不是讲解知识点，整篇文章建立在默认已经会的基础之上，然后提出一些个人见解。
最短路
此时的 SPFA 显得不再重要了（，咱们进入正题，说一下 dijkstra。
（堆优化的）迪杰的本质是贪心，他依赖于一种叫“最优子结构”的东西（其实就是贪心常说的局部最优达到全局最优），首先观察一下代码：
inline void dij (int x) {
priority_queue < pair < int ,int > > q ;
memset (dis ,0x3f ,sizeof dis) ;
dis[x] = 0 ;
q.push (make_pair (0 ,x)) ;
while (! q.empty ()) {
int cur = q.top ().second ;
q.pop () ;
if (vis[cur]) continue ;
vis[cur] = true ;
for (int i = head[cur] ;i ;i = e[i].nxt) {
int nex = e[i].to ;
if (dis[nex] > dis[cur] + e[i].val) {
dis[nex] = dis[cur] + e[i].val ;
q.push (make_pair (-dis[nex] ,nex)) ;
}
}
}
}
这份代码看起来并不那么可靠，所以我制作了一张简单图：
假设我们已经知道了 \(1\rightarrow2\rightarrow4\) 的距离是 \(2\)，也就是 \(dis_4=2\)，然后我们发现 \(4\) 在堆里的位置比 \(3\) 靠前（也就是说其实我们还没有用 \(3\) 去查看 \(4\)），但是我们仍然可以直接用 \(dis_4\) 去更新其他的点，为什么？注意到全都是正边，因为 \(1\rightarrow2\rightarrow4\) 已经短于 \(1\rightarrow3\) 了，所以无论 ? 是多少，\(1\rightarrow3\rightarrow4\) 肯定不会更短，也就是说我们完全没有必要等到 \(3\) 的时候在再用 \(4\) 更新别人。
也就是说 dij 选择性忽略了“还没枚举到的点”的情况
这也解释了为什么 dij 不支持负边权，因为如果可以是负数那么我们的贪心策略就不再正确。
同时也解释了为什么不能跑最长路，因为（比如）\(1\rightarrow2\rightarrow4\) 已知的比 \(1\rightarrow3\) 长（我们还没有遍历到 \(3\)），但是这并不代表 \(1\rightarrow3\rightarrow4\) 一定比已知的 \(1\rightarrow2\rightarrow4\) 短，所以我们不可以这个时候更新。
但是如果原图全是负边求最长路你全都取反跑最短路也不是不行（。