首页 > 代码库 > 最短路径
最短路径
要说最短路，先来说说最长路，理解了最长路问题之后，才能透彻理解最短路的几个算法。
最大化问题在线性结构、树型结构里面可以轻松构造无后效性的最优子结构解决，但是在图结构里面就很麻烦，原因是顺着一个点推下去之后，图结构中还存在另一个点亦可到达此点，可能推翻前面存的结果。所以要对整个图进行Relax。
最短路径算法中，Dijkstra，Bellman-Ford，Floyd的Relax操作都使用了动态规划的思想，具体点就是著名的“三角形不等式”。
现在拿最短路的几个算法来求试试最长路问题，Dijkstra只是从根向儿子推了一遍，所以Dijkstra算法建立最优子结构无法求解最长路。
Bellman-Ford 暴力地把图中所有边松弛（Relax）V-1次，把所有的状态都用三角形不等式Relax了一遍，结果是对的，当然其中做了很多没必要的计算。
SPFA同上，只不过SPFA确立的一个Relax最大量的上界，对Bellman-Ford做了剪枝优化。
多源最长路是个NP-Hard问题，floyd无法求解。
另外Dijkstra还使用贪心的思想，导致贪负权路的结果是错的。
竞赛中，单源最短路径最偷懒的是Bellman-Ford优化过的SPFA方法，可以有效处理负权路/判断负环，甚至可以逆向求定源最长路，判断正环。
不过SPFA看图的结构，稀疏图平均复杂度低于O(n^2), 最差复杂度会退化渐进至O（VE) 。这时候就没有优先队列优化过的Dijkstra速度快了O(nlogn)。
所以没有负权还是乖乖Dijkstra吧，优先队列的优化一定得加上，O（n）和O（logn）的扩张线简直是天壤之别，
Tips： 求最短路时，第一要注意是有向图还是无向图，第二就是初始化。存图推荐链式前向星，邻接表的话使用vector比较简洁（缺点是clear慢）。
三大模板。
1. SPFA
bool SPFA(){ queue<int> Q; memset(vis,0,sizeof(vis)); memset(cnt,0,sizeof(cnt)); for(int i=1;i<=n;i++) d[i]= (i==1?0:inf); // 最长路反过来 Q.push(1); cnt[1]++; while(!Q.empty()) { int x=Q.front();Q.pop(); vis[x]=false; //! for(int i=0;i<G[x].size();i++) //x和邻接所有v进行Relax， { if(d[x]+G[x][i].w<d[G[x][i].p]) //倒过来求最长路 { d[G[x][i].p]=d[x]+G[x][i].w; if(!vis[G[x][i].p]) { vis[G[x][i].p]=true; Q.push(G[x][i].p); if(++cnt[G[x][i].p]>n) return true; //判断负环/正环 } } }}
2. 优先队列优化的Dijkstra（链式前向星版，这里要郑重推荐一下链式前向星，我在跑树链剖分的时候用vector邻接表跑了4s+,TLE了。但是用了链式前向星之后，只用了1.5s）
struct Edge{ int to,next,w;}edge[maxn*2];struct status{ int d,p; status(int d,int p):d(d),p(p) {} bool operator < (const status &a ) const {return d > a.d;}};int head[maxn],vis[maxn],d[maxn],n;void dijkstra(int s){ memset(vis,0,sizeof(vis)); priority_queue<status> Q; Q.push(status(0,s)); for(int i=1;i<=n;i++) d[i]=(i==s?0:inf); while(!Q.empty()) { status tt=Q.top(); Q.pop(); int x=tt.p; if(vis[x]) continue; vis[x]=true; for(int i=head[x];i!=-1;i=edge[i].next) { if(d[x]+edge[i].w<d[edge[i].to]) { d[edge[i].to]=d[x]+edge[i].w; Q.push(status(d[edge[i].to],edge[i].to)); } } }}
3. Floyd（带上最小环）
void floyd(){ memset(G,1,sizeof(G));//1=inf memset(d,1,sizeof(d)); for(int i=1;i<=n;i++) G[i][i]=G[i][i]=d[i][i]=d[i][i]=0; int MIN=1<<28; for(int i=1; i<=m; i++) { scanf("%d%d%d",&u,&v,&w); G[u][v]=G[v][u]=d[u][v]=d[v][u]=w; //无向图写法 } for(int k=1; k<=n; k++) { for(int i=1; i<k; i++) //求最小环 for(int j=1; j<i; j++) MIN=min(MIN,d[i][j]+G[j][k]+G[k][i]); for(int i=1; i<=n; i++) for(int j=1; j<=n; j++) //无向图 j=i+1 d[i][j]=d[i][j]<d[i][k]+d[k][j]?d[i][j]:d[i][k]+d[k][j]; } if(MIN>=inf) printf("No solution.\n");//无最小环}
@练习题
hdu3790（双权最短路）
POJ1062（比较坑爹，自己百度题解）
POJ1125（单源里面最长的，多源里面最短 的，orz）
POJ1860（逆向Bellman-Ford，判断正环）
POJ3259（背景是霍金的虫洞，挺有趣的题，意思比较难懂，前进是正权是 无向图，后退是负权是有向图）
vijos1391（挺奇葩的题，Relax不再是累加路径，而是取最小值）。
最短路径