本文共 8274 字，大约阅读时间需要 27 分钟。
单源最短路算法——Dijkstra
优点：复杂度比较稳定
缺点：无法解决存在负权的问题
具体思路：Dijkstra是基于一种贪心的策略，首先用数组dis记录起点到每个结点的最短路径，再用一个数组保存已经找到最短路径的点。然后，从dis数组选择最小值，则该值就是源点s到该值对应的顶点的最短路径，并且把该点记为已经找到最短路，此时完成一个顶点，再看这个点能否到达其它点（记为v），将dis[v]的值进行更新，不断重复上述动作，将所有的点都更新到最短路径。
因为采用链式向前星存图，需要学习一下
大佬写的链式向前星的讲解
head[x] 里的 x 指的是点的序号
head 和 e[i].next 存的都是cnt（结构体下标）， head[x] 存的 cnt 是 x 节点的最后一个儿子，即在e[cnt]中，next存的是上一个儿子的cnt值，w存的指向当前儿子边的权值，to存的儿子的节点序号
每一个节点第一次指向的儿子时，存的next值都是0；因为每一次添加新的起点时，都是先将head[x] 赋给第一个儿子，新的head[x]的值是0；而后head[x]才更新为第一个儿子的结构体下标。
// 朴素 Dijkstra (n²)#include using namespace std;typedef long long ll;const ll inf = 0x7fffffff;const int N = 1e6 + 9;ll n, m , s, cnt;ll v[N], dis[N], head[N];struct Edge{ int w, to, nextt;}edge[N];void add(int x,int y, int z){ edge[++cnt].w = z; edge[cnt].to = y; edge[cnt].nextt = head[x]; head[x] = cnt;}int main(){ cin >> n >> m >> s; for(int i = 1; i <= m; ++i) { int a, b, c; scanf("%d %d %d", &a, &b, &c); add(a, b, c); } for(int i = 1; i <= n; ++i) dis[i] = inf; dis[s] = 0; // Dijkstra模板 int pos = s; while(!v[pos]) { v[pos] = 1; for(int i = head[pos]; i != 0; i = edge[i].nextt) { int tmp = edge[i].to; if(dis[tmp] > dis[pos] + edge[i].w && !v[tmp])// 更新可以更新的最短距离 { dis[tmp] = dis[pos] + edge[i].w; } } ll Min = inf; for(int i = 1; i <= n; ++i)// 更新下一次的pos { if(dis[i] < Min && !v[i]) Min = dis[i], pos = i; } } for(int i = 1; i <= n; ++i) cout << dis[i] << " "; return 0;}
在dis数组中选择最小值时，我们可以用一些数据结构来进行优化。
// Dijkstra 堆优化// 可以过标准版#include using namespace std;typedef long long ll;const int N = 1e6 + 9;const int inf = 0x7fffffff;ll dis[N], n, m, s;bool v[N];int head[N], cnt;struct Edge{ int to, nextt, w;}e[N];priority_queue >, greater > > q;//priority_queue , vector >,greater > > q;// 和上边一样ac// 队列里的元素按照 pair first 的值 从小到大出队的顺序排列 即堆的顺序// 这时候取出最小的dis下标复杂度是O（1），即堆顶元素// 但是优先队列维护会有 O（log n） 的复杂度void add_edge(int x, int y, int z){ e[++cnt].w = z; e[cnt].to = y; e[cnt].nextt = head[x]; head[x] = cnt;}int main(){ for(int i = 1; i <= N; ++i) dis[i] = inf; cin >> n >> m >> s; for(int i = 1; i <= m; ++i) { int a, b ,c; scanf("%d %d %d", &a, &b, &c); add_edge(a, b, c); } dis[s] = 0; q.push(make_pair(0,s)); while(!q.empty()) { int now = q.top().second; q.pop(); if(v[now]) continue;// 这个删了会tle v[now] = 1; for(int i = head[now]; i; i = e[i].nextt) { int tmp = e[i].to; if(!v[tmp] && dis[tmp] > dis[now] + e[i].w) { //这里的 !v[tmp] 删了一样ac // dij算法是基于贪心的思想，当v[tmp] = 0 时，也就是已经以tmp节点向后更新最短路了，所以tmp节点的最短路肯定被更新完了 dis[tmp] = dis[now] + e[i].w; q.push(make_pair(dis[tmp], tmp)); // 更新了就入队 } } } for(int i = 1; i <= n; ++i) cout << dis[i] << " "; return 0;}
取个设值double型，对值取log，求log和最小，即为积最小
设一个二维数组存路径
然后倒着遍历，因为我们存的是每一个点的上一个点
#include #include #include #include #include #include using namespace std;typedef long long ll;const int N = 1e6 + 9;const ll inf = 1e12;const int mod = 9987;int head[N], cnt;bool v[N];int n, m;double dis[N];struct Edge{ int to, nextt; double w;}e[N];ll pre[N][5];// 存路径 void add_edge(int x, int y, int z){ e[++cnt].w = z; e[cnt].to = y; e[cnt].nextt = head[x]; head[x] = cnt;}void dijkstra(){ priority_queue >, greater > > q; memset(dis,0x7f,sizeof(dis)); dis[1] = 0; q.push(make_pair(0,1)); while(!q.empty()) { int x = q.top().second; q.pop(); if(v[x]) continue; v[x] = 1; for(int i = head[x]; i; i = e[i].nextt) { int tmp = e[i].to; if(dis[tmp] > dis[x] + log(e[i].w)) { dis[tmp] = dis[x] + log(e[i].w); pre[tmp][0] = x; pre[tmp][1] = e[i].w;// 存当前边值和上一个节点编号 q.push(make_pair(dis[tmp],tmp)); } } }}int main(){ cin >> n >> m; for(int i = 1; i <= n; ++i) { int a, b;double c; scanf("%d %d %lf", &a, &b, &c); add_edge(a, b, c); } dijkstra(); ll ans = 1;int pos = n;// 倒着遍历路径 while(pos != 1) { ans *= (ll)pre[pos][1]; ans %= mod; pos = pre[pos][0]; } cout << ans << endl; return 0;}
要求出任意两个人之间距离的最大值，也就是全源最短路
这是个无向图啊！！！ 建立双向的表
#include #include #include #include #include using namespace std;const int N = 4e3 + 9;// 注意开两倍数组，无向图const int inf = 0x7fffffff;int n, m;int dis[N];bool v[N];int ans;int head[N];struct Edge{ int to, nextt, w;}e[N];int cnt;void addedge(int a, int b){ e[++cnt].to = b; e[cnt].w = 1; e[cnt].nextt = head[a]; head[a] = cnt;}void Dijkstra(int s){ priority_queue >, greater > >q; for(int i = 1; i <= n; ++i) dis[i] = inf; memset(v,0,sizeof(v)); dis[s] = 0; q.push(make_pair(0,s)); while(!q.empty()) { int now = q.top().second; q.pop(); if(v[now]) continue; v[now] = 1; for(int i = head[now]; i; i = e[i].nextt) { int tmp = e[i].to; if(dis[tmp] > dis[now] + e[i].w) { dis[tmp] = dis[now] + e[i].w; q.push(make_pair(dis[tmp],tmp)); } } }}int main(){ cin >> n >> m; for(int i = 1; i <= m; ++i) { int a, b; scanf("%d %d", &a, &b); addedge(a, b); addedge(b, a);// 无向图！！！ 建立双向的 } for(int i = 1; i <= n; ++i) { Dijkstra(i); for(int j = 1; j <= n; ++j) { if(dis[j] == inf){ cout << -1 << endl;return 0; } ans = max(dis[j], ans); //cout << dis[j] << " "; } //cout << endl; } cout << ans << endl; return 0;}
SPFA算法
1.只让当前点能到达的点入队
2.
如果一个点已经在队列里，便不重复入队 3.如果一条边未被更新，那么它的终点不入队
SPFA也可以判负权环，我们可以用一个数组记录每个顶点进队的次数，当一个顶点进队超过n次时，就说明存在负权环。（这与Bellman-Ford判负权环的原理类似）
主要比赛的时候可能出毒瘤数据，卡SPFA
// spfa// 能过个弱化版#include using namespace std;typedef long long ll;const int N = 1e6+ 9 ;const int inf = 0x7fffffff;int n, m , s;int head[N], cnt, dis[N];int v[N];queue q;struct Edge{ int w, to ,nextt;}e[N];void add_edge(int x, int y, int z){ e[++cnt].w = z; e[cnt].to = y; e[cnt].nextt = head[x]; head[x] = cnt;}int main(){ for(int i = 1; i <= N-1; ++i) dis[i] = inf; cin >> n >> m >> s; for(int i = 1; i <= m; ++i) { int a, b , c; scanf("%d %d %d", &a, &b, &c); add_edge(a, b, c); } dis[s] = 0; q.push(s); while(!q.empty()) { int x = q.front(); q.pop(); v[x] = 0;// 已经入过队的恢复为0, 只需要维护队列里的不在入队，出队的也会再入队 for(int i = head[x]; i; i = e[i].nextt) { int tmp = e[i].to; if(dis[tmp] > dis[x] + e[i].w) { dis[tmp] = dis[x] + e[i].w; if(!v[tmp])// !v[tmp] 这个只能放在里边，不能合并到上一个if里 { // 遇到可更新dis的就更新，但入队必须是不在队伍里的 v[tmp] = 1; q.push(tmp); } } } } for(int i = 1; i <= n; ++i) cout << dis[i] << " "; return 0;}
Johnson算法
思路就是 spfa从虚拟节点0跑一遍，然后重设边权
再跑n遍 dijkstra
详细看洛谷题解
// 全源最短路#include #include #include #include #include #include #define INF 1e9using namespace std;typedef long long ll;const int N = 1e6 + 9;const ll inf = 1e9;int n, m;int cnt, head[N];bool v[N];// 初始为0，spfa先用一遍 ，而dij每次用都清0 可以共用 ll h[N], dis[N];int t[N];struct Edge{ int w, to, nextt;}e[N];void add_edge(int x, int y, int z){ e[++cnt].w = z; e[cnt].to = y; e[cnt].nextt = head[x]; head[x] = cnt;}bool spfa(int s){ queue q; memset(h,63,sizeof(h)); h[s] = 0; q.push(s); while(!q.empty()) { int x = q.front(); q.pop(); v[x] = 0; for(int i = head[x]; i; i = e[i].nextt) { int tmp = e[i].to; if(h[tmp] > h[x] + e[i].w) { h[tmp] = h[x] + e[i].w; if(!v[tmp]) { v[tmp] = 1; q.push(tmp); t[tmp]++; if(t[tmp] == n + 1) return true;// 某个节点入队 n+1 次 就说明有负环 // t[tmp] >= n 会wa一个点 } } } } return false;}void dijkstra(int s){ priority_queue , vector >, greater > > q; memset(v,0,sizeof(v));// 注意v数组清0 for(int i = 1; i <= n; ++i) dis[i] = inf; dis[s] = 0; q.push(make_pair(0,s)); // 记得初始化 while(!q.empty()) { int now = q.top().second; q.pop(); if(v[now]) continue; v[now] = 1; for(int i = head[now]; i; i = e[i].nextt) { int tmp = e[i].to; if(dis[tmp] > dis[now] + e[i].w) { dis[tmp] = dis[now] + e[i].w; q.push(make_pair(dis[tmp],tmp)); } } }}int main(){ cin >> n >> m; for(int i = 1; i <= m; ++i) { int a, b, c; scanf("%d %d %d", &a, &b, &c); add_edge(a, b, c); } for(int i = 1; i <= n; ++i) add_edge(0, i, 0); if(spfa(0)){ // 判断负环 cout << -1 << endl;return 0; } for(int u = 1; u <= n; u++) for(int i = head[u]; i; i = e[i].nextt) e[i].w += h[u] - h[e[i].to]; // 加上 u -> e[i].to 的距离 for (int i = 1; i <= n; i++) { dijkstra(i); ll ans = 0; for (int j = 1; j <= n; j++) { if (dis[j] == inf) ans += 1ll* j * inf; else ans += 1ll*j * (dis[j] + h[j] - h[i]); } // 减去 i -> j 的距离 cout << ans << endl; } return 0;}/*5 71 2 41 4 102 3 74 5 34 2 -23 4 -35 3 4*/
转载地址：http://dwfm.baihongyu.com/