最短路基础算法:Dijkstra,SPFA,Floyd,Bellman-ford
Dijkstra一般情况慢于SPFA,但特殊情况下SPFA会被卡,而Dijkstra不会.该算法不能处理负权边. SPFA编写难度小于Dijkstra,且可处理负权边
Luogu P3371 【模板】单源最短路径（弱化版） Luogu P4779 【模板】单源最短路径（标准版）(卡SPFA)
1.Dijkstra 使用dis[ ]数组存放该点到起始点的最短距离,每次寻找所有dis[ ]中最小的节点,并以该节点更新其他节点,复杂度O(n2).寻找最小节点可使用堆优化,优化时间复杂度至O(nlogn).
不使用堆优化:
//Dijkstra #include<bits/stdc++.h> using namespace std; struct EDGE { int id,v; }; list<EDGE>node[10005]; int dis[10005]; int vis[10005]; int n,m,s,x,y,z; int main() { cin>>n>>m>>s; int maxn=(pow(2,31)-1); for(int i=1;i<=n;i++){dis[i]=maxn;} for(int i=1;i<=m;i++){ cin>>x>>y>>z; node[x].push_back({y,z}); } dis[s]=0; queue<int>q; q.push(s); while(!q.empty()) { int now=q.front();q.pop(); vis[now]=1; int minv=1e9,minid=-1; for(auto& to:node[now]){ if(dis[now]+to.v<dis[to.id]){ dis[to.id]=dis[now]+to.v; } } for(int i=1;i<=n;i++){ if(dis[i]<minv&&!vis[i]){ minv=dis[i];minid=i; } } if(minid!=-1){q.push(minid);} } for(int i=1;i<=n;i++){ cout<<dis[i]<<" "; } return 0; }使用堆优化:
//Dijkstra,堆优化 #include<bits/stdc++.h> #define MAXN 10005 #define INF 2147483647 using namespace std; struct Dijkstra { struct EDGE { int id,v; }; struct Int { int id,dis; bool operator <(const Int&b)const{ return dis>b.dis; } }; priority_queue<Int>q; list<EDGE>node[MAXN]; int dis[MAXN]; int vis[MAXN]; void init(int n){ for(int i=1;i<=n;i++){dis[i]=INF;} } void add(int u,int v,int w){ node[u].push_back({v,w}); } void dijkstra(int s){ dis[s]=0; q.push({s,0}); while(!q.empty()) { Int now=q.top();q.pop(); if(vis[now.id])continue; vis[now.id]=1; for(auto& to:node[now.id]){ if(dis[now.id]+to.v<dis[to.id]){ dis[to.id]=dis[now.id]+to.v; q.push({to.id,dis[to.id]}); } } } } }; int n,m,s,x,y,z; Dijkstra a; int main() { cin>>n>>m>>s; a.init(n); for(int i=1;i<=m;i++){ cin>>x>>y>>z; a.add(x,y,z); } a.dijkstra(s); for(int i=1;i<=n;i++){ cout<<a.dis[i]<<" "; } return 0; }2.SPFA 无负权值时不要作死用SPFA，多半会被卡 建立一个队列，初始时队列里只有起始点，再建立一个表格记录起始点到所有点的最短路径（该表格的初始值要赋为极大值，该点到他本身的路径赋为0）。然后执行松弛操作，用队列里有的点作为起始点去刷新到所有点的最短路，如果刷新成功且被刷新点不在队列中则把该点加入到队列最后。重复执行直到队列为空。
判断有无负环： 如果某个点进入队列的次数超过N次则存在负环（SPFA无法处理带负环的图）
最差情况时间复杂度:O(NM)
//SPFA #include<bits/stdc++.h> #define INF 2147483648-1 #define MAXN 10005 using namespace std; struct SPFA { struct To { int id,v; }; vector<To>node[MAXN]; int inq[MAXN],inq_cnt[MAXN]; int dis[MAXN]; int n; void init(int n){ for(int i=1;i<=n;i++){dis[i]=INF;inq[i]=0;inq_cnt[i]=0;} this->n=n; } void add(int x,int y,int v){ node[x].push_back({y,v}); } int spfa(int s){//(int n,int start) queue<int>q; q.push(s); inq[s]=1;dis[s]=0; while(!q.empty()){ int now=q.front();q.pop(); inq[now]=0; if(inq_cnt[now]>=n){return 0;}//有负环,不能找到最短路 for(auto& i:node[now]){ if(dis[now]+i.v<dis[i.id]){ dis[i.id]=dis[now]+i.v; if(!inq[i.id]){ q.push(i.id);inq[i.id]=1; inq_cnt[i.id]++; } } } } return 1;//能找到最短路 } }; int n,m,s,x,y,z; SPFA spfa; int main() { cin>>n>>m>>s; spfa.init(n); for(int i=1;i<=m;i++){ cin>>x>>y>>z; spfa.add(x,y,z); } spfa.spfa(s); for(int i=1;i<=n;i++){ cout<<spfa.dis[i]<<" "; } return 0; }3.Floyd 可求任意两点的最短路,可处理负权边,复杂度O(n3).模板
for(int k=1;k<=n;k++){ for(int i=1;i<=n;i++){ for(int j=1;j<=n;j++){ a[i][j] = min(a[i][j],a[i][k]+a[k][j]); } } }4.Bellman-ford 思路： 1.初始化时将起点s到各个顶点v的距离dist(s->v)赋值为∞，dist(s->s)赋值为0； 2.后续进行最多n-1次遍历操作(n为顶点个数),对所有的边进行松弛操作;
所谓的松弛，以边ab为例，若dist(a)代表起点s到达a点所需要花费的总数， dist(b)代表起点s到达b点所需要花费的总数,weight(ab)代表边ab的权重， 若存在: (dist(a) +weight(ab)) < dist(b) 则说明存在到b的更短的路径,s->...->a->b,更新b点的总花费为(dist(a) +weight(ab))，父节点为a3.遍历都结束后，若再进行一次遍历，还能得到s到某些节点更短的路径的话，则说明存在负环路。
这个算法太慢了，SPFA最差情况和它速度一样，可能判断负环会比SPFA快一些。判断负环就完成循环以后再找一次，若还能更新，则有负环。
//BellMan-ford #include<bits/stdc++.h> using namespace std; struct EDGE { int a,b,v; };vector<EDGE>edge; long long dis[10005]; int n,m,s,u,v,w; int main() { std::ios::sync_with_stdio(false); cin>>n>>m>>s; int maxn=pow(2,31)-1; for(int i=1;i<=n;i++){dis[i]=maxn;} for(int i=1;i<=m;i++){ cin>>u>>v>>w; edge.push_back({u,v,w}); } dis[s]=0; for(int i=1;i<=n-1;i++){ //这里可以优化：找到所有的最短路后就可以退出了，即无法松弛就可以退出了 for(auto& i:edge){ if(dis[i.a]+i.v<dis[i.b]){dis[i.b]=dis[i.a]+i.v;} } } for(int i=1;i<=n;i++){cout<<dis[i]<<" ";} return 0; }