图论技能get！
一个超强大的建图网站
最短路问题
1.dij算法
用于单源最短路
仅适用于没有负边权的情况
初始化dis数组为inf，dis【起点】=0；
tool：priority-queue（按dis升序）
先把起点放进队列
每次取出排头now，枚举它能去的地方v；
如果——
dis[v]>dis[now]+p[i].w
说明目前从now走到v更优，就更新它，并入队
最后now出列，并永远不要回来（用人话说就是判重）
模板
void dij(){
for(int i=1;i<=n;i++) dis[i]=INT_MAX;
memset(jd,0,sizeof(jd));
dis[s] = 0;
priority_queue<pr,vector<pr>,greater<pr> >q;
q.push(make_pair(0,s));
int tot=0;
while(!q.empty()){
int now=q.top().second;q.pop();
if(jd[now]) continue;
jd[now]=1;
for(int i=fi[now];~i;i=p[i].nxt){
int v=p[i].to;
//printf("#%d %d %d\n",p[i].nxt,now,v);
if(dis[v]>dis[now]+p[i].w){
dis[v]=dis[now]+p[i].w;
q.push(make_pair(dis[v],v));
}
}
}
}
（关于链式前向星存图，请移步这里
证明
因为没有负权
所以当前dis最小的值以后不可能从别的地方再更新
所以每次都取最小的，每个就只需取一次（n）
备注
因为优先队列操作复杂度带个log，所以
总复杂度为：O（nlogn）
从证明也可以看出，dij只适用于正权，那么有负权是怎么办？
可以使用——
2.SPFA
“spfa已经死了”
和dij其实很类似，只是他不用优先队列，也不判重，只要枚举出度满足上面那个关系式就可以进队（当然，已经在的不要再进了）
当队列为空结束
代码
void spfa(double x){
queue<int>q;
mem(jd,1);
for(int i=1;i<=n;i++) dis[i]=(double)inf;
mem(nm,0);
for(int i=0;i<m;i++){
p[i].w -= x;
}
for(int i=1;i<=n;i++){
q.push(i);
}
while(!q.empty()){
int now=q.front();q.pop();
jd[now]=0;
for(int i=fi[now];~i;i=p[i].nxt){
int v=p[i].to;
if(dis[v]>=dis[now]+p[i].w){
dis[v]=dis[now]+p[i].w;
if(jd[v]==0) q.push(v);
}
}
}
for(int i=0;i<m;i++) p[i].w +=x;
return;
}
证明
因为不去重，队列还是空了，说明已经没有任何两对满足更新的关系式~~（暴力有什么好证明的）~~
备注
复杂度十分 玄学 不稳定
在特殊构造和稠密图可能卡成O（mn）
直接裂开（2018NOIP血的教训）
所以尽量还是用dij吧
floyd
多源！！！！
代码《过于冗长》，直接看着代码解释吧。。。
代码
for(int k = 1; k <= n; ++k)
for(int i = 1; i <= n; ++i)
for(int j = 1; j <= n; ++j)
dp[i][j] = min(dp[i][j], dp[i][k] + dp[k][j]);
证明
（想不明白直接背）
dp[i][j][k]是从i到j经过中转编号最大值为k的最短路
那么dp[i][j][k]更新到dp[i][j][k+1]就是看看经过k+1会不会更优呗
所以就是上面那个状态转移方程
最后dp[i][j][n]就是最终的最短路
踩蛋
（这个不是王建国写的）
负环
如果存在一个总权值为负值的环，那么所有能碰到该环的两点的最短路都会是无穷小（大风车吱吖吱悠悠的转 ）
此时spfa就会出现死循环
所以需要特殊判断负环
如果一条路径经过的点大于n，显然它是经过了环
而你算着算着最短路它为啥溜号去跑环了呢？一定是出现了负环
从而进行判断
关于代码实现，我们可以在更新时加一行转移：
nm[v]=nm[now]+1
代码
bool spfa(){
queue<int>q;
mem(jd,0);
for(int i=1;i<=n;i++) dis[i]=inf;
mem(nm,0);
q.push(1);
jd[1]=1;
dis[1]=0;
while(!q.empty()){
int now=q.front();q.pop();
jd[now]=0;
for(int i=fi[now];~i;i=p[i].nxt){
int v=p[i].to;
if(dis[v]>dis[now]+p[i].w){
dis[v]=dis[now]+p[i].w;
nm[v]=nm[now]+1;
if(jd[v]==0) q.push(v);
if(nm[v]>=n){
return true;
}
}
}
}
return false;
}