【图论】总结
一、最短路
最短路是满足最优子结构性质的。可以用反证法证明。
1. Dijkstra
Dijkstra基于贪心思想。
SRE实战 互联网时代守护先锋，助力企业售后服务体系运筹帷幄！一键直达领取阿里云限量特价优惠。两个集合。$S$中的点是已经确定了到源点的最短路的，$V-S$是未知的。此时，$V-S$集合中的$d$全部都是由$S$得来的，换句话说，这些d值对应的最短路统统经过S内的点。
每一步从$V-S$中选择一个$d$最小的点$i$加入$S$中，即最短路得以确定。这个最短路一定是由$S$中的点构成的，并且是$S$中所能构成的最优的，因为它是由$S$中所有与它相邻的点松弛后得来的。利用反证法：如果它还不是最优的，则存在一个点$p$使得
dis[$i$->$p$->起点]<dis[$i$->起点] （1）
前者等于$dis(i,p)+d[p]$，后者等于$d[i]$。然而就目前状况来看，$d[i]<d[p]$，故（1）不成立。或曰$d[p]$还未确定，然而$d[p]$再松弛也不可能小于$d[i]$，因为它再要松弛也是被$i$或$d$比i更大的点松弛了。
因此有结论
dis[$i$->起点]≤dis[$i$->$p$->起点] （2）
也正是因为（2）式，使得Dijkstra只能用于边权非负的图。因为如果$dis(i,p)<0$就不一定满足了。
由于每次都是从一集合中选择$d$最小的元素，故可以用堆来优化。一个点可能会被多条边松弛，因此可能同时在堆中有好几个。此时需要剔除后来的。有一种不用done数组的方法，就是判断堆中存的d值是否大于数组中的d值。如果堆中的偏大则剔除。
以每个点为起点进行松弛，最多松弛成功$m$次。每一次加入堆的复杂度是$logn$。因此Dijkstra堆优化的复杂度是$O(mlogn)$
#include <cstdio> #include <algorithm> #include <cstring> #include <queue> using namespace std; inline int read(){ int x(0),w(1); char c = getchar(); while(c^'-' && (c<'0'||c>'9')) c = getchar(); if(c == '-') w = -1, c = getchar(); while(c>='0' && c<='9') x = (x<<3) + (x<<1) + c - '0', c = getchar(); return x*w; } struct node{ int u,d; }; int n,m,s,x,y,z,d[100010]; int head[100010],nxt[200010],to[200010],cost[200010],cnt; priority_queue <node> q; inline bool operator < (const node& a, const node& b){ return a.d > b.d; } inline void add(int u, int v, int w){ to[++cnt] = v; cost[cnt] = w; nxt[cnt] = head[u]; head[u] = cnt; } inline void dijkstra(int S){ for(int i = 0; i <= n+1; ++i) d[i] = 2000000000; d[S] = 0; q.push((node){S,0}); int u,D; while(!q.empty()){ u = q.top().u, D = q.top().d; q.pop(); if(D > d[u]) continue; for(int i = head[u]; i; i = nxt[i]){ if(d[u]+cost[i] < d[to[i]]){ d[to[i]] = d[u]+cost[i]; q.push((node){to[i],d[to[i]]}); } } } } int main(){ n = read(), m = read(), s = read(); for(int i = 1; i <= m; ++i){ x = read(), y = read(), z = read(); add(x,y,z); } dijkstra(s); for(int i = 1; i <= n; ++i){ printf("%d ",d[i]); } return 0; }template_Dijkstra
2. Bellman-Ford / SPFA
也就是Bellman-Ford算法的队列优化。针对Dijkstra无法处理的负权情况。
显然，最短路上一定不存在环。那么最短路一定是一个生成树状物。因此最多包含$n-1$条边。从每个点出发松弛一次称为一次迭代。可以通过迭代$n-1$来求得最短路。因为我们已经考虑到了所有可能边数的最短路，因此显然正确。这就是Bellman-Ford。复杂度显然$O(nm)$
然而每一次都从所有点出发松弛没有必要，有些点可能在上一次并没有被松弛，即$d$没有改变，那就没有必要再去做一次。换句话说，我们发现只有上一轮被松弛了的点才可能去松弛别人。因此我们用一个队列来保存上一轮被松弛的点。当然，最坏情况依然是$O(nm)$。这就是SPFA。
从很多方面，SPFA都和BFS很像。而BFS可以来求无权图的最短路。因为BFS求的最短路是边数的最短路。无权图中边数即路径长度。因此第一次松弛时的最短路一定最优。而当图有了边权，第一次松弛以后可能会被再次松弛，因为有可能边数更多，路径长度却更小。这使得一个点可能会重复进队，这是和BFS不同的。相应的，SPFA的复杂度就更大了。
也因此还需要一个bool数组来判断一个点是否在队中。如果已经在队中，再去进队就没有意义了。因为和Dijkstra不同，这里的队列只保存了点的编号，而$d$是与点的编号对应的，因此在松弛时其实已经将队中的点的$d$修改到更优了。
关于负环，很显然如果迭代次数超过$n-1$即有负环。然而在SPFA中好像不是那么容易计算迭代次数的，因为第几次迭代都一股脑儿在队列里了。那么就判断松弛次数吧，反正肯定不会错。另外，有向图中某点出发可能无法到达负环。
#include <cstdio> #include <algorithm> #include <cstring> using namespace std; inline int read(){ int x(0),w(1); char c = getchar(); while(c^'-' && (c<'0'||c>'9')) c = getchar(); if(c == '-') w = -1, c = getchar(); while(c>='0' && c<='9') x = (x<<3) + (x<<1) + c - '0', c = getchar(); return x*w; } int T,n,m,x,y,z,h,t,d[4010],q[4000010],inq[4010],dep[4010]; int head[4010],nxt[8010],to[8010],cost[8010],cnt; inline void init(){ memset(head,0,sizeof(head)); memset(nxt,0,sizeof(nxt)); memset(to,0,sizeof(to)); memset(cost,0,sizeof(cost)); cnt = 0; } inline void add(int u, int v, int w){ to[++cnt] = v, cost[cnt] = w; nxt[cnt] = head[u]; head[u] = cnt; } inline bool SPFA(int S){ memset(d,0x3f,sizeof(d)); memset(inq,0,sizeof(inq)); memset(dep,0,sizeof(dep)); d[S] = h = t = 0; q[++t] = S; int u; while(h < t){ ++h; u = q[h]; inq[u] = 0; for(int i = head[u]; i; i = nxt[i]){ if(d[u]+cost[i] < d[to[i]]){ d[to[i]] = d[u]+cost[i]; dep[to[i]] = dep[u]+1; if(dep[to[i]] > n-1) return 1; if(!inq[to[i]]){ inq[to[i]] = 1; q[++t] = to[i]; } } } } return 0; } int main(){ T = read(); while(T--){ init(); n = read(), m = read(); for(int i = 1; i <= m; ++i){ x = read(), y = read(), z = read(); add(x,y,z); if(z>=0) add(y,x,z); } if(SPFA(1)) printf("YE5\n"); else printf("N0\n"); } return 0; }template_SPFA与负环
