虽然最短路算法非常基础，但是每年都会遇到一点问题，每次都要重新想一遍，比较头疼。于是在这里集中思考一下。
关于Dijkstra算法
众所周知，dijkstra算法不能跑含有负权边的图。稍微从算法的原理来构造一下，很容易构造出答案错误的例子(4个点即可)，这也是Bellman-Ford(或SPFA)存在的理由。dijkstra的思想很简单，就是采用步步为营的策略，每一步扩展的节点一定当前最短路。而当有负权边的时候，可能实际的最短路会绕一大圈，导致某个被访问过的点不再去更新别的点。
比较正常的dijkstra写法：
void dijk(int s){
memset(dis,0x3f,sizeof(dis));
memset(vis,0,sizeof(vis));
dis[s]=0;
priority_queue<pair<int,int> > qu;
qu.push(make_pair(0,s));
while (qu.size()){
int u=qu.top().second, mc=-qu.top().first;
qu.pop();
if (vis[u]) continue;
vis[u]=1;
for (int e=head[u];e;e=nxt[e])
if (!vis[to[e]] && mc+co[e]<dis[to[e]]){
dis[to[e]]=mc+co[e];
qu.push(make_pair(-dis[to[e]],to[e]));
}}}
这个算法在正权图上最坏是(V+E)logV的复杂度，因而在接近完全图的稠密图上可能慢于原始Dijkstra的V^2算法。
我们发现一个节点仍有可能多次入堆，这是STL堆不支持decrease_key的折衷写法。不过最坏情况也就堆中存在O(E)个元素，问题不大。但是10/11行的vis标记是必要的，保证一个已被标记的点无谓地去尝试更新其他节点。删去它会导致算法复杂度提高一个量级。
另一种简单写法是换成 if (dis[u]<=mc) continue; 它的效果在正权图上与vis标记等价。而且你甚至会发现这样写在负权图上都能算出正确结果(岂不美哉?)。确实如此，在负权图上这个算法确实能多次更新得到正确的最短路，但不幸的是时间复杂度是指数阶的。
考虑这样一个模块，来自点1的更新会导致点2先更新出一个次小值，再从点3更新一次。如果把这样的模块级联，并调整边权使点2下一级的点先于点3更新，那么总更新次数将达到2^n。
如果追求极致的复杂度，也可以用更高级的堆来实现Dijkstra算法。比如Fibonacci堆支持O(1)插入，最终复杂度为O(E+VlogV)，只不过大部分情况这么做没有必要。有理论证明在随机图上二叉堆的Dijkstra复杂度为O(E+V*log(E/V)logV)。
SPFA算法(Bellman-Ford的队列优化)
SPFA这个名字是早期OI遗留下来的不正确的产物。原因可能是早期OI不严谨也不那么毒瘤。如果要求Pascal选手写最短路还附带实现一个二叉堆显然不太合理。那时候sort都没有，很多人的快排代码很容易退化成n^2，一般不会有人去试图卡这个点。
但是关于SPFA它死了？乱讲，算负权图的时候你还不得把它抬出来。除非你决定既然最坏O(VE)了那就破罐子破摔直接上暴力的Bellman-Ford(严格O(VE))。
况且在比较随机的情形下，SPFA有时甚至快于dijkstra。
不过，一些试图优化SPFA的技巧确实可能弄巧成拙。SLF优化、LLL优化在随机图上确实有一些效果，在正权图上尽可以这么做，不会改变最坏的复杂度。但在负权图上，则有可能会达到致命的指数阶复杂度。
弄巧成拙的原因是，SPFA正确名称是Bellman的队列优化，而这些优化却破坏了队列结构。Bellman-Ford的思想很简单，每一步尝试松弛每一条边，或者说从所有顶点更新一次到其他顶点的路程。而最短路不可能经过超过n个节点，所以总复杂度为O(VE)。SPFA的想法也很简单，Bellman-Ford中仅之前被更新过的点才有可能更新别的点，所以可以组织成一个队列。即正常SPFA的更新操作是原Bellman-Ford的一个子集。
但这些想当然的优化会破坏Bellman-Ford的操作顺序。我曾试图把SPFA的队列换成优先队列，有些人称之为“堆优化的SPFA”，并通过了洛谷上卡SPFA的单源最短路(标准版)。但是仔细观察就会突然发现这个代码与前面没有vis标记的dijkstra算法并无二致，那么指数级复杂度就立刻出现了。同样，SLF和LLL优化也会出现大同小异的问题。
总而言之，如果真的用到这些有问题的代码，一般是出题人有问题。以HDU6611为例，在所给的时限下甚至没有正确的算法。HDU6611的正常的做法是做一个4000个点，4000000条边，增广次数不超过10次的网络流。但因为卡SPFA的最短路，出题人使用了不带vis标记的dijkstra(或称为堆优化的SPFA) 作为标解。把SPFA的队列换成栈也能快速通过此题。一些人为通过此题少连了一些边来加速，因为数据弱确实可以通过。
poj上有道判断负环的题，用“dfs版本的SPFA”可在规定的时间内通过，其本质也是把队列换成栈，以最坏时间指数级为代价换取更快的平均运行时间。
或者准确地说，这些优化有一点存在的意义，但最好不应称为优化。这些算法的行为更接近“启发式搜索”，归到搜索或许更合适。
tql!!!