第48期：图论

第48期：图论

参考：

Bellman-ford算法详解——负权环分析_anlian523的博客-CSDN博客_bellman-ford​​​​​​

最短路径问题---Dijkstra算法详解_William-CSDN博客_dijkstra

最短路径问题---Floyd算法详解_William-CSDN博客_floyd算法

最短路径问题---SPFA算法详解_William-CSDN博客_spfa算法

单源最短路径 - 题解 - 洛谷

Dijkstra算法

适合稠密图；只适用于不含负权边的图；时间复杂度上限为(朴素)；加上堆优化之后更是具有的时间复杂度。

1.【模板】单源最短路径（标准版） - 洛谷 

Dijkstra堆优化

#include<bits/stdc++.h>
using namespace std;
const int maxn=1e5+10,maxm=5e5+10,INF=INT_MAX;struct edge{int to,dis,next;
}; 
edge e[maxm];
int head[maxn],dis[maxn],cnt;
bool vis[maxn];
int n,m,s;inline void add_edge(int u,int v,int d){cnt++;e[cnt].dis=d;e[cnt].to=v;e[cnt].next=head[u];head[u]=cnt;
}struct node{int dis;int pos;bool operator < (const node &x) const{return x.dis<dis;}
};priority_queue<node> q;inline void dijkstra(){dis[s]=0;q.push((node){0,s});while(q.size()){node tmp&#p(); q.pop();int x=tmp.pos,d=tmp.dis;if(vis[x]) continue;vis[x]=1;for(int i=head[x];i;i=e[i].next){int y=e[i].to;if(dis[y]>dis[x]+e[i].dis){dis[y]=dis[x]+e[i].dis;if(!vis[y]){q.push((node){dis[y],y});}}}}
}int main(){cin>>n>>m>>s;for(int i=1;i<=n;++i) dis[i]=INF;for(int i=0;i<m;++i){int u,v,d; cin>>u>>v>>d;add_edge(u,v,d);}dijkstra();for(int i=1;i<=n;i++) cout<<dis[i]<<" ";return 0;
}

Dijkstra  一般线段树优化

#include<bits/stdc++.h>
using namespace std;
const int maxn=1e5+10,maxm=2e5+10,INF=0x3f3f3f3f;int n,m,s;
struct edge{int v,w,next;
}e[maxm];
int head[maxn];void addEdge(int u,int v,int w){static int cnt=0;e[++cnt]=(edge){v,w,head[u]};head[u]=cnt;
}
#define ls (o<<1)
#define rs (o<<1|1)
int minv[maxn<<2],minp[maxn<<2];void pushup(int o){if(minv[ls]<=minv[rs]) minv[o]=minv[ls],minp[o]=minp[ls];else minv[o]=minv[rs],minp[o]=minp[rs];
}
void build(int o,int l,int r){if(l==r){minv[o]=INF;minp[o]=l;return;}int mid=(l+r)>>1;build(ls,l,mid);build(rs,mid+1,r);pushup(o);
}
void modify(int o,int l,int r,int p,int w){if(l==r){minv[o]=w;return;}int mid=(l+r)>>1;if(p<=mid) modify(ls,l,mid,p,w);else modify(rs,mid+1,r,p,w);pushup(o);
}int dis[maxn];
void dijkstra(int s){build(1,1,n);modify(1,1,n,s,0);memset(dis,0x3f,sizeof dis);dis[s]=0;while(minv[1]!=INF){int u=minp[1];modify(1,1,n,u,INF);for(int i=head[u];i;i=e[i].next){int v=e[i].v,w=e[i].w;if(dis[v]>dis[u]+w){dis[v]=dis[u]+w;modify(1,1,n,v,dis[v]);}}}
}int main(){cin>>n>>m>>s;for(int i=1;i<=m;++i){int u,v,d; cin>>u>>v>>d;addEdge(u,v,d);}dijkstra(s);for(int i=1;i<=n;i++) cout<<dis[i]<<" ";return 0;
}

Dijkstra zkw线段树优化

#include <cctype>
#include <cstdio>
#include <climits>
#include <algorithm>#define rep(I, A, B) for (int I = (A); I <= (B); ++I)
#define dwn(I, A, B) for (int I = (A); I >= (B); --I)
#define erp(I, X) for (int I = head[X]; I; I = next[I])template <typename T> inline void read(T& t) {int f = 0, c = getchar(); t = 0;while (!isdigit(c)) f |= c == '-', c = getchar();while (isdigit(c)) t = t * 10 + c - 48, c = getchar();if (f) t = -t;
}
template <typename T,  Args>
inline void read(T& t, Args&... args) {read(t); ); 
}
template <typename T> void write(T x) {if (x < 0) x = -x, putchar('-');if (x > 9) write(x / 10);putchar(x % 10 + 48);
}
template <typename T> void writeln(T x) {write(x);puts("");
}
template <typename T> inline bool chkMin(T& x, const T& y) { return y < x ? (x = y, true) : false; }
template <typename T> inline bool chkMax(T& x, const T& y) { return x < y ? (x = y, true) : false; }const int maxn = 1e5 + 207, maxm = 2e5 + 207, inf = INT_MAX;
int v[maxm], w[maxm], head[maxn], next[maxm], tot;
int dist[maxn], mp[maxn << 2], M = 1;
int n, m, s;inline void ae(int x, int y, int z) { v[++tot] = y; w[tot] = z; next[tot] = head[x]; head[x] = tot; }
inline int cmp(int a, int b) { return dist[a] < dist[b] ? a : b; }
inline void build(int n) {while (M < n + 2) M <<= 1;mp[0] = n + 1;
}
inline void modify(int x, int nv) {for (int i = x + M; dist[mp[i]] > nv; i >>= 1)mp[i] = x;dist[x] = nv;
}
inline void del(int x) {for (mp[x += M] = 0, x >>= 1; x; x >>= 1)mp[x] = cmp(mp[x << 1], mp[x << 1 | 1]);
}
inline void dijkstra(int s) {rep(i, 0, n) dist[i] = inf;build(n); modify(s, 0);rep(t, 1, n - 1) {int x = mp[1]; del(x);// 这里没有对dist[v[i]]赋值，赋值操作在modify函数里进行，与上一个代码有所区别erp(i, x) if (dist[v[i]] > dist[x] + w[i])modify(v[i], dist[x] + w[i]);}
}int main() {read(n, m, s);rep(i, 1, m) {int x, y, z; read(x, y, z); ae(x, y, z);}dijkstra(s);rep(i, 1, n) write(dist[i]), putchar(' ');puts("");return 0;
}