前置知识
Dijkstra 算法
Dijkstra（/ˈdikstrɑ/或/ˈdɛikstrɑ/）算法由荷兰计算机科学家 E. W. Dijkstra 于 1956 年发现，1959 年公开发表。是一种求解 非负权图 上单源最短路径的算法。
流程
将结点分成两个集合：已确定最短路长度的点集（记为 $S$ 集合）的和未确定最短路长度的点集（记为 $T$ 集合）。一开始所有的点都属于 $T$ 集合。
初始化 $dis(s)=0$，其他点的 $dis$ 均为 $+\infty$。
然后重复这些操作：
- 从 $T$ 集合中，选取一个最短路长度最小的结点，移到 $S$ 集合中。
- 对那些刚刚被加入 $S$ 集合的结点的所有出边执行松弛操作。
直到 $T$ 集合为空，算法结束。
时间复杂度
有多种方法来维护 1 操作中最短路长度最小的结点，不同的实现导致了 Dijkstra 算法时间复杂度上的差异。
- 暴力：不使用任何数据结构进行维护，每次 2 操作执行完毕后，直接在 $T$ 集合中暴力寻找最短路长度最小的结点。2 操作总时间复杂度为 $O(m)$，1 操作总时间复杂度为 $O(n^2)$，全过程的时间复杂度为 $O(n^2 + m) = O(n^2)$。
- 二叉堆：每成功松弛一条边 $(u,v)$，就将 $v$ 插入二叉堆中（如果 $v$ 已经在二叉堆中，直接修改相应元素的权值即可），1 操作直接取堆顶结点即可。共计 $O(m)$ 次二叉堆上的插入（修改）操作，$O(n)$ 次删除堆顶操作，而插入（修改）和删除的时间复杂度均为 $O(\log n)$，时间复杂度为 $O((n+m) \log n) = O(m \log n)$。
- 优先队列：和二叉堆类似，但使用优先队列时，如果同一个点的最短路被更新多次，因为先前更新时插入的元素不能被删除，也不能被修改，只能留在优先队列中，故优先队列内的元素个数是 $O(m)$ 的，时间复杂度为 $O(m \log m)$。
- Fibonacci 堆：和前面二者类似，但 Fibonacci 堆插入的时间复杂度为 $O(1)$，故时间复杂度为 $O(n \log n + m) = O(n \log n)$，时间复杂度最优。但因为 Fibonacci 堆较二叉堆不易实现，效率优势也不够大[^1]，算法竞赛中较少使用。
- 线段树：和二叉堆原理类似，不过将每次成功松弛后插入二叉堆的操作改为在线段树上执行单点修改，而 1 操作则是线段树上的全局查询最小值。时间复杂度为 $O(m \log n)$。
在稀疏图中，$m = O(n)$，使用二叉堆实现的 Dijkstra 算法较 Bellman-Ford 算法具有较大的效率优势；而在稠密图中，$m = O(n^2)$，这时候使用暴力做法较二叉堆实现更优。
正确性证明
下面用数学归纳法证明，在 所有边权值非负 的前提下，Dijkstra 算法的正确性。
简单来说，我们要证明的，就是在执行 1 操作时，取出的结点 $u$ 最短路均已经被确定，即满足 $D(u) = dis(u)$。
初始时 $S = \varnothing$，假设成立。
接下来用反证法。
设 $u$ 点为算法中第一个在加入 $S$ 集合时不满足 $D(u) = dis(u)$ 的点。因为 $s$ 点一定满足 $D(u)=dis(u)=0$，且它一定是第一个加入 $S$ 集合的点，因此将 $u$ 加入 $S$ 集合前，$S \neq \varnothing$，如果不存在 $s$ 到 $u$ 的路径，则 $D(u) = dis(u) = +\infty$，与假设矛盾。
于是一定存在路径 $s \to x \to y \to u$，其中 $y$ 为 $s \to u$ 路径上第一个属于 $T$ 集合的点，而 $x$ 为 $y$ 的前驱结点（显然 $x \in S$）。需要注意的是，可能存在 $s = x$ 或 $y = u$ 的情况，即 $s \to x$ 或 $y \to u$ 可能是空路径。
因为在 $u$ 结点之前加入的结点都满足 $D(u) = dis(u)$，所以在 $x$ 点加入到 $S$ 集合时，有 $D(x) = dis(x)$，此时边 $(x,y)$ 会被松弛，从而可以证明，将 $u$ 加入到 $S$ 时，一定有 $D(y)=dis(y)$。
下面证明 $D(u) = dis(u)$ 成立。在路径 $s \to x \to y \to u$ 中，因为图上所有边边权非负，因此 $D(y) \leq D(u)$。从而 $dis(y) \leq D(y) \leq D(u)\leq dis(u)$。但是因为 $u$ 结点在 1 过程中被取出 $T$ 集合时，$y$ 结点还没有被取出 $T$ 集合，因此此时有 $dis(u)\leq dis(y)$，从而得到 $dis(y) = D(y) = D(u) = dis(u)$，这与 $D(u)\neq dis(u)$ 的假设矛盾，故假设不成立。
因此我们证明了，1 操作每次取出的点，其最短路均已经被确定。命题得证。
注意到证明过程中的关键不等式 $D(y) \leq D(u)$ 是在图上所有边边权非负的情况下得出的。当图上存在负权边时，这一不等式不再成立，Dijkstra 算法的正确性将无法得到保证，算法可能会给出错误的结果。
二分答案
解题的时候往往会考虑枚举答案然后检验枚举的值是否正确。若满足单调性，则满足使用二分法的条件。把这里的枚举换成二分，就变成了「二分答案」。
关于一种 $O((n+m)log^2n)$ 的单源的最短路优秀做法 ：
Dijkstra 算法一直被广大 OIer 们奉为圭臬，然而，今天它的不败神话被推翻了(详见：卡 Dijstra 的问题)。那么我们现在需要一个更加优秀的算法。
于是，这种$O((n+m)log^2n)$ 的单源的最短路优秀做法应运而生！
具体做法
设起点为 $S$， 终点为 $T$, 当前二分的答案为 $mid$ 。
首先二分当前最短路的长度，然后再从 $S$ 开始跑一遍Dijkstra， 求出到T的最短路长度 $W$, 若 $W < mid$ 则缩小二分上界， 反之亦然。
这样就得到了优秀的 $O(nlog^2n)$ 最短路算法。
算法的正确性证明 ：
当二分的值为 $mid$ 时， 对于任何二分的值 $x > mid$，存在一种长度小于 $x$ 的路径， 所以答案具有单调性 ， 可以用二分解决！
历史意义
将单源最短路径以更加优秀的思想视作为线性题目并进行二分答案。使得算法结果更加精准，优秀。打破了dijkstra对于单源最短路径问题的统治甚至是垄断的局面。使得广大的 OIer 从禁锢的思想中解放出来，激发了更多的 OIer 对于当今古老陈旧的算法进行创新性改良，创造性改变。
算法评价
在广大 OIer 都在唾弃某 spfa 算法的时候，本 dijkstra 站了出来，打破了dijkstra的独裁，使 spfa 和 dijkstra 具有了同等的地位，增加了最短路算法的多元性，让二分 + dijkstra 走到广大人民群众中去。
代码
#include <cstdio>
#include <queue>
#include <cstring>
using namespace std;
const int N = 2e5 + 5;
int n, m, pos;
int ver[N], nex[N], head[N], vis[N], dis[N], edge[N];
struct NODE{ int id, dis; };
void add(int x, int y, int z){
ver[++pos] = y; edge[pos] = z; nex[pos] = head[x]; head[x] = pos;
}
bool operator < (NODE a, NODE b){
return a.dis > b.dis;
}
bool check(int Start, int End, int mid){
priority_queue<NODE> Que;
Que.push((NODE){Start, 0});
memset(dis, 0x3f, sizeof(dis));
memset(vis, 0, sizeof(vis));
dis[Start] = 0;
vis[Start] = 1;
while(Que.size()){
int x = Que.top().id; Que.pop();
for(int i = head[x]; i; i = nex[i]){
int y = ver[i];
if(dis[y] > dis[x] + edge[i]){
dis[y] = dis[x] + edge[i];
if(!vis[y]){
vis[y] = 1;
Que.push((NODE) {y, dis[y]});
}
}
}
vis[x] = 0;
}
return dis[End] >= mid;
}
int Get_Min_Road_Dijkstra_Algorithm(const int Start, const int End){
const int INF = 0x3f3f3f3f;
int Left = 0, Right = INF;
while(Left < Right){
int mid = (Left + Right + 1) >> 1;
check(Start, End, mid);
if(mid <= dis[End]) Left = mid;
else Right = mid - 1;
}
return Left;
}
int main(){
scanf("%d %d", &n, &m);
for(int i = 1; i <= m; ++i){
int x, y, z;
scanf("%d %d %d", &x, &y, &z);
add(x, y, z);
}
int Start, End;
scanf("%d %d", &Start, &End);
printf("%d\n", Get_Min_Road_Dijkstra_Algorithm(1, n));
return 0;
}可以输入以下数据进行验证 ：
4 3 1 2 1 2 3 1 3 4 1 1 4
程序运行结果为 ：
3
发现答案是正确的。
心路历程
我们曾经将课本上的Dijkstra奉为圭臬，认为它便是单源最短路径的最佳解决方案。但，直到我发现有这么一道最短路径问题，Djikstra并不能将其AC通过。它动摇了我对Dijkstra算法的信任。不过这也让我开始思考：如何找出单源最短路径的更优解？我们一行人便开始思索。虽然Dijkstra有堆优化，但其优化效果还是十分有限。我们尝试着组合算法，就如同大多数人对于一般算法的优化一般。几乎从头到尾依次考虑了一遍，终是不能如愿。
陈旧的算法仍然禁锢这年轻的我们的思维，以至于使我们无论如何都逃脱不了Dijkstra故有基于贪心的思维模式。
在Dijkstra的思维模式内，永远不能够想出超过Dijkstra的算法。就如同，虚拟机的性能一定弱于物理机一般。Dijkstra，就必须脱离图论思维的桎梏。不破不立，唯有过正才能矫枉。唯有向死而生，才能焕发出新的希望。
于是，我们改进思维方式，开始以另一种形式去思考单元最短路径问题。战国有屈原上下而求索，我们何得不能同屈原一般。江山代有人才出，独领风骚数百年。谁说在某不知名学校就不能出现引领风骚的人才？我不答应，我们更不答应。
风萧萧兮易水寒，壮士一去兮不复返。踏上了破立创新的道路，必然要遭到无数人的不解和谩骂。
不过面对学术界的反对，我们从未有过放弃的念头，我们也从未后悔。因为我们知道我们所发现的可能不是真理，却能够引领在座的各位年轻人们打破桎梏去探索真理。去改进真理。去树立真理。虽然站在巨人的肩膀上是稳妥的选择，也是聪明的选择。但历史总是需要勇者有勇气去成为巨人，树立新的高度。
我时刻虚心接受批评，亦时刻高傲的去面对无端的谩骂和质疑。
对于我们来说，可能最终极的目标就是搞出好成绩，通过好名次，辅助自己考上好大学。至于对学术的贡献便是以后的事情了。但以后以后，终为飘渺，终为虚妄。只要踏上了研究的道路，无论何时何地何条件何身份。心中都应该有一份责任感，为这个世界发一份光。后来者在黑暗的道路上前行，我们有义务去为他们点亮前方的灯。
雾中求索，终有大同。
拨雾开云，初遇明朗。
萧萧成雨，击水中流。
甚穿见岸，訇然中开。
雄关漫道真如铁，而今迈步从头越。我们终究找到了胜利的归途。
参考文献
https://oi-wiki.org/graph/shortest-path
https://oi-wiki.org/basic/binary
联合作者
@ASteepMountain
