最短路相关模板、总结
大牛博客，值得一刷。配合LRJ训练指南最短路相关UVA题目。
http://www.blogbus.com/vanquisher-logs/73268586.html
1.
Dijkstra算法
自己写一遍才知道可能犯的错误，囧。
HDU2544大水题一枚。 http://acm.hdu.edu.cn/showproblem.php?pid=2544
//1.注意INF的取值，不仅仅是最大边长度 2.注意W[i][j]的清空void Dijk(){ memset(v,0,sizeof(v)); for(int i=1;i<=n;i++) d[i]=(i==1)?0:INF; for(int i=1;i<=n;i++) { int x,m=INF; for(int j=1;j<=n;j++) { if(!v[j]&&d[j]<m) x=j,m=d[j]; //x:当前选出的最小点 } v[x]=1; for(int j=1;j<=n;j++) { if(d[j]>(d[x]+w[x][j])) d[j]=d[x]+w[x][j]; } }}边(x,y)上的松弛操作
if(d[j]>(d[x]+w[x][j]))
{
d[j]=d[x]+w[x][j];
fa[j]=x;
}
附POJ2387 http://poj.org/problem?id=2387
： Dijk不适合有重边的情况，（显然），然后需要自己判一下，囧。
或者只读入w[a][b]=c即可，但是要当a>b时，swap(a,b);
具体同临接表。自己发现，具体证明算导应该有吧。
临接表做法，适用与稀疏图，先给每条边编号，next[e]表示e的下一条边
总感觉自己写的模板没问题，可至今未过题
，先放这。。现在回来看明白了，这个邻接表只适合单向图，双向图要建两次。
void adj(){ memset(visit,0,sizeof(visit)); memset(next,-1,sizeof(next)); for(int i=1;i<=n;i++) first[i]=-1,d[i]=(i==1)?0:INF; for(int i=1;i<=m;i++) { scanf("%d%d%d",&u[i],&v[i],&w[i]);//别忘交换。 if(u[i]>v[i]) swap(u[i],v[i]); next[i]=first[u[i]]; first[u[i]]=i; } for(int i=1;i<=n;i++) //这地方要循环n次 { int x,temp=INF; for(int j=1;j<=n;j++) if(!visit[j]&&d[j]<temp) x=j,temp=d[j]; visit[x]=1; for(int e=first[x];e!=-1;e=next[e]) { if(d[v[e]]>(d[x]+w[e])) d[v[e]]=d[x]+w[e]; } }}Dijkstra不能计算负权的原因：
dijkstra由于是贪心的，每次都找一个距源点最近的点（dmin），然后将该距离定为这个点到源点的最短路径（d[i]<--dmin）；但如果存在负权边，那就有可能先通过并不是距源点最近的一个次优点（dmin'），再通过这个负权边L(L<0)，使得路径之和更小（dmin'+L<dmin）,则dmin'+L成为最短路径，并不是dmin，这样dijkstra就被囧掉了。比如n=3，邻接矩阵：0，3，43，0，-24，-2，0用dijkstra求得d[1，2]=3，事实上d[1，2]=2，就是通过了1-3-2使得路径减小。
2、Floyd算法
//先初始化d[i][i]=0,其他为INF for(int k=0;k<n;k++) for(int i=0;i<n;i++) for(int j=0;j<n;j++) { if(d[i][j]>(d[i][k]+d[k][j])) d[i][j]=d[i][k]+d[k][j]; }1.注意重边，选最小的边2.注意如果自身到自身返回03.注意双向边 //这三条不管是用那个算法都注意一下。
Floyd算法边权可正可负，不适合大量顶点。
有向图的传递闭包：HDU1181
3、Bellman-ford算法 时间复杂度O（n*m）
For i:=1 to |V|-1 do //v为顶点数For 每条边(u,v)∈E do //对每条边进行遍历 Relax(u,v,w);For每条边(u,v)∈E do If dis[u]+w<dis[v] Then Exit(False)可以判断是否存在负权环。
o(∩∩)o...哈哈，偶终于明白了。。
Bellman-ford也不能直接照着LRJ的代码敲，自己得加两种情况，就是考虑是有向图还是无向图。（每种最短路算法都要这样。
）
妹的啊，Bellman-ford是判断负权环的，存在负权环可以来回走，负权边就不可以来回走了？
偶果然明白了，这个负权环是总值为负值的环，而不是存在负值的环。
这样的话，为什么Bellman-ford能判断负环我也就明白了。但这只能针对单向图。 双向图（即无向图）是不能这么判的，因为双向图只要一条边就可以来回走。
总之自己在做的时候注意是单向图还是双向图，是否有负权！》》BF算法局限还是挺大的。
Dijkstra算法和Bellman算法思想有很大的区别：
Dijkstra算法在求解过程中，源点到集合S内各顶点的最短路径一旦求出，则之后不变了，修改的仅仅是源点到T集合中各顶点的最短路径长度。
Bellman算法在求解过程中，每次循环都要修改所有顶点的dist[]，也就是说源点到各顶点最短路径长度一直要到Bellman算法结束才确定下来。 如果存在从源点可达的负权值回路，则最短路径不存在，因为可以重复走这个回路，使得路径无穷小。 在Bellman算法中判断是否存在从源点可达的负权值回路的方法：
4、spfa算法
由于要对点的每一条边进行枚举,故采用邻接表时时间复杂度为O(kE),采用矩阵时时间复杂度为O(kV^2)SPFA算法有两个优化算法 SLF 和 LLL： SLF：Small Label First 策略，设要加入的节点是j，队首元素为i，若dist(j)<dist(i)，则将j插入队首，否则插入队尾。 LLL：Large Label Last 策略，设队首元素为i，队列中所有dist值的平均值为x，若dist(i)>x则将i插入到队尾，查找下一元素，直到找到某一i使得dist(i)<=x，则将i出对进行松弛操作。 SLF 可使速度提高 15 ~ 20%；SLF + LLL 可提高约 50%。 在实际的应用中SPFA的算法时间效率不是很稳定，为了避免最坏情况的出现，通常使用效率更加稳定的Dijkstra算法。
spfa未优化邻接表版 ： 一定得注意是单向图还是双向图。
void spfa(){ for(int i=1;i<=n;i++) d[i]=(i==1?0:INF); memset(inq,0,sizeof(inq)); q.push(1); while(!q.empty()) { int x=q.front();q.pop(); inq[x]=false; for(int e=first[x];e!=-1;e=next[e]) { if(d[v[e]]>d[x]+w[e]) { d[v[e]]=d[x]+w[e]; if(!inq[v[e]]) { inq[v[e]]=true; q.push(v[e]); } } } }}SPFA(slf优化)//使用deque双向队列void Spfa(){ d[S]=0; v[S]=true; deque <int> q; for(q.push_back(S);!q.empty();) { int x=q.front(); q.pop_front(); for(int k=head[x];k!=-1;k=el[k].next) { int y=el[k].y; if(d[y]>d[x]+el[k].c) { d[y]=d[x]+el[k].c; if(!v[y]) { v[y]=true; if(!q.empty()) { if(d[y]>d[q.front()]) q.push_back(y); else q.push_front(y); } else q.push_back(y); } } } v[x]=false; } return ;}那一般情况下 E << v^2 so 可以用spfa。。
那要是V非常多直接FLOYD呗。
附：
1.Dijkstra队列代码模板
struct Edge {int from,to,dist;}; struct Node { int d,u; bool operator <(const Node &a) const { return a.d<d;//从小到大排序。 } }; int n,m; //点数和边数，用n表示，e不能和m冲突 vector<Edge> edges;//边列表 vector<int> G[maxn];//每个结点出发的边编号（从0开始编号） bool done[maxn];//是否已永久编号 int d[maxn];//s到各个点的距离 int p[maxn];//最短路中的上一条边 void init() { for(int i=0;i<n;i++) G[i].clear();//清空邻接表 edges.clear(); } void addedge(int from,int to,int dist) //如果是无向，每条无向边需调用两次addedge { edges.push_back((Edge){from,to,dist}); int temp=edges.size(); G[from].push_back(temp-1); } void dijk(int s) { priority_queue<Node> q; for(int i=0;i<n;i++) d[i]=INF; d[s]=0; memset(done,0,sizeof(done)); q.push((Node){0,s}); while(!q.empty()) { Node x=q.top(); q.pop(); int u=x.u; if(done[u]) continue; done[u]=true; for(int i=0;i<G[u].size();i++) { Edge &e=edges[G[u][i]]; if(d[e.to]>d[u]+e.dist) { d[e.to]=d[u]+e.dist; p[e.to]=G[u][i]; q.push((Node){d[e.to],e.to}); } } } }