最短路常用模板整理

单源最短路，Dijkstra算法，适用于无负权边情况，简单时间复杂度O（n^2），堆优化时间复杂度为O((m+n)log n)、变形也可求最短路径最大权值和最长路径最小权值

int cost[MAX_V][MAX_V]; //图的邻接矩阵 int d[MAX_V];//顶点s（起点）到各点的最短距离 bool used[MAX_V];//是否已经访问过 int V;//顶点数 int prev[MAX_V];//前驱顶点 void Dijkstra(int s){ fill(d,d+V,INF); fill(used,used+V,false); fill(prev,prev+V,-1); d[s]=0; while(true){ int v=-1; for(int u=0;u<V;u++) { if(!used[u]&&(v==-1||d[u]<d[v])) v=u; } if(v==-1) break; used[v]=true; for(int u=0;u<V;u++){ d[u]=min(d[u],d[v]+cost[v][u]); if(d[u]>d[v]+cost[v][u]){ prev[u]=v; } } } } vector<int> get_path(int t){ vector<int> path; for(;t!=-1;t=prev[t]) path.push_back(t); reverse(path.begin(),path.end()); return path; }

STL 队列实现

struct edge{int to,cost;}; typedef pair<int,int> P; //first是最短距离，second是顶点编号 int V; vector<edge> G[MAX_V]; int d[MAX_V]; void Dij(int s){ //通过指定参数，使优先队列按照first从小到大出序列 prioruty_queue<P,vrctor<P>,greater<P>> que; fill(d,d+V,INF); d[s]=0; que.push(P(0,s)); while(!que.empty()){ P p=que.top();que.pop(); int v=p.second; if(d[v]<p.first) continue; for(int i=0;i<G[v].size();i++){ edge e=G[v][i]; if(d[e.to]>d[v]+e.cost){ d[e.to]=d[v]+e.cost; que.push(P(d[e.to],e.to)); } } } }

任意两点最短路，Floyd算法，适用于无负权环的情况，时间复杂度为O（n^3）

int d[MAX_V][MAX_V]; //无法到达时，权值为INF，主对角线为0 int V; //顶点数 void Floyd(){ for(int k=0;k<V;k++){ for(int i=0;i<V;i++){ for(int j=0;j<V;j++){ d[i][j]=min(d[i][j],d[i][k]+d[k][j]); } } } }

但是Floyd是无法判断负权边存在的情况的，接下来介绍的bellman-ford适用于负权边，复杂度为O（nm），点少的时候用起来比SPFA好写很多，找负环边的时候可以用二分

#include<bits/stdc++.h> #define ll long long #define INF 0x3f3f3f3f using namespace std; struct V{ int u,v; ll w; }edge[600]; ll dis[600]; int n,m; bool bellman_ford(){ memset(dis,INF,sizeof(dis)); for(int i=1;i<n;++i){ for(int j=1;j<=m;++j){ if(dis[edge[j].v]>dis[edge[j].u]+edge[j].w){ dis[edge[j].v]=dis[edge[j].u]+edge[j].w; } } } for(int j=1;j<=m;++j){ if(dis[edge[j].v]>dis[edge[j].u]+edge[j].w) return false; } return true; }

还有个时间复杂度未知的算法为SPFA，就是写起来太复杂了，返回false代表有负环，可以判断有没有负环，但无法处理有负环的图

#include "bits/stdc++.h" using namespace std; const int maxN = 200010 ; struct Edge { int to , next , w ; } e[ maxN ]; int n,m,cnt,p[ maxN ],Dis[ maxN ]; int In[maxN ]; bool visited[ maxN ]; void Add_Edge ( const int x , const int y , const int z ) { e[ ++cnt ] . to = y ; e[ cnt ] . next = p[ x ]; e[ cnt ] . w = z ; p[ x ] = cnt ; return ; } bool Spfa(const int S) { int i,t,temp; queue<int> Q; memset ( visited , 0 , sizeof ( visited ) ) ; memset ( Dis , 0x3f , sizeof ( Dis ) ) ; memset ( In , 0 , sizeof ( In ) ) ; Q.push ( S ) ; visited [ S ] = true ; Dis [ S ] = 0 ; while( !Q.empty ( ) ) { t = Q.front ( ) ;Q.pop ( ) ;visited [ t ] = false ; for( i=p[t] ; i ; i = e[ i ].next ) { temp = e[ i ].to ; if( Dis[ temp ] > Dis[ t ] + e[ i ].w ) { Dis[ temp ] =Dis[ t ] + e[ i ].w ; if( !visited[ temp ] ) { Q.push(temp); visited[temp]=true; if(++In[temp]>n)return false; } } } } return true; } int main ( ) { int S , T ; scanf ( "%d%d%d%d" , &n , &m , &S , &T ) ; for(int i=1 ; i<=m ; ++i ) { int x , y , _ ; scanf ( "%d%d%d" , &x , &y , &_ ) ; Add_Edge ( x , y , _ ) ; } if ( !Spfa ( S ) ) printf ( "FAIL!\n" ) ; else printf ( "%d\n" , Dis[ T ] ) ; return 0; }