目录
一.Dijkstra算法（不能处理存在负权的清况）
4 6 1
1 2 2
2 3 2
2 4 1
1 3 5
3 4 3
1 4 4
0 2 4 3
1.堆（优先队列）优化版本：（慢，占用内存还大）
#include<bits/stdc++.h>
using namespace std;
#define debug(x) cout<<"# "<<x<<" "<<endl;
typedef long long ll;
const ll mod=2147483647000;
const ll N=500007;
struct Edge
{
ll v,w,next;//v:目的地,w:距离,next:下一个节点
}G[N];
ll head[N],cnt,n,m,s;
ll dis[N];//存距离
inline void addedge(ll u,ll v,ll w)//链式前向星存图
{
cnt++;
G[cnt].w=w;
G[cnt].v=v;
G[cnt].next=head[u];
head[u]=cnt;
}
struct node
{
ll d,u;//d是距离u是起点
bool operator<(const node& t)const//重载运算符
{
return d>t.d;
}
};
inline void Dijkstra()
{
for(register int i=1;i<=n;++i)dis[i]=mod;//初始化
dis[s]=0;
priority_queue<node>q;//堆优化
q.push((node){0,s});//起点push进去
while(!q.empty())
{
node tmp=q.top();q.pop();
ll u=tmp.u,d=tmp.d;
if(d!=dis[u])continue;//松弛操作剪枝
for(register int i=head[u];i;i=G[i].next)//链式前向星
{
ll v=G[i].v,w=G[i].w;
if(dis[u]+w<dis[v])//符合条件就更新
{
dis[v]=dis[u]+w;
q.push((node){dis[v],v});//沿着边往下走
}
}
}
}
int main()
{
scanf("%lld %lld %lld",&n,&m,&s);
for(register int i=1;i<=m;++i)
{
ll x,y,z;
scanf("%lld %lld %lld",&x,&y,&z);
addedge(x,y,z);//建图
}
Dijkstra();
for(register int i=1;i<=n;++i)
printf("%lld ",dis[i]);
printf("\n");
return 0;
}
2.普通线段树优化版本（一般块）
#include<algorithm>
#include<iostream>
#include<cstring>
#include<cstdio>
#include<cmath>
#include<queue>
#define maxn 100005
#define inf 2147483647
using namespace std;
typedef long long ll;
int read() {
int x = 0, f = 1, ch = getchar();
while(!isdigit(ch)) {if(ch == '-') f = -1; ch = getchar();}
while(isdigit(ch)) x = (x << 1) + (x << 3) + ch - '0', ch = getchar();
return x * f;
}
int n, m;
struct edge {
int to, w, nxt;
edge() {}
edge(int t, int ww, int nn) {to = t, w = ww, nxt = nn;}
}e[maxn << 1];
int head[maxn], k = 0;
void add(int u, int v, int w) {e[k] = edge(v, w, head[u]); head[u] = k++;}
ll ans[maxn];
struct node {
ll dis; int x;
node() {}
node(ll d, int xx) {dis = d, x = xx;}
}dis[maxn << 2];
//建树初始化，主要是编号也要返回所以要先预处理一下
void build(int p, int l, int r) {
if(l == r) {dis[p].x = l; return;}
int mid = l + r >> 1;
build(p << 1, l, mid); build(p << 1 | 1, mid + 1, r);
dis[p].x = dis[p << 1].x;
}
void change(int p, int l, int r, int x, int y) {
if(l == r) {dis[p].dis = y; return;}
int mid = l + r >> 1;
if(x <= mid) change(p << 1, l, mid, x, y);
else change(p << 1 | 1, mid + 1, r, x, y);//单点修改的板子操作
if(dis[p << 1].dis < dis[p << 1 | 1].dis) dis[p] = dis[p << 1];
else dis[p] = dis[p << 1 | 1];
}
//因为用距离得到最小，但是需要的是编号，所以返回node
node ask(int p, int l, int r, int ls, int rs) {
if(ls <= l && r <= rs) {return dis[p];}
int mid = l + r >> 1; node ans = node(inf, 0), tmp;
if(ls <= mid) ans = ask(p << 1, l, mid, ls, rs);
if(rs > mid) {
node tmp = ask(p << 1 | 1, mid + 1, r, ls, rs);
if(ans.dis > tmp.dis) ans = tmp;
}
return ans;
}
int S;
void dij() {
for(int k = 1; k < n; k++) {//n-1次够用的。虽然我也不知道为什么最后n次跑的比n-1次还要快……
register int u = ask(1, 1, n, 1, n).x;
for(int i = head[u]; ~i; i = e[i].nxt) {
register int v = e[i].to;
if(ans[u] + e[i].w < ans[v]) {//最短路更新
ans[v] = ans[u] + e[i].w, change(1, 1, n, v, ans[v]);//单点修改
}
}
change(1, 1, n, u, inf);//取出来过后要赋值INF，以免再次取用
}
}
signed main() {
memset(head, -1, sizeof head);
n = read(), m = read(), S = read();
for(int u, v, w, i = 1; i <= m; i++) u = read(), v = read(), w = read(), add(u, v, w);
//初始化
for(int i = 1; i <= (n << 2); i++) dis[i].dis = inf;
for(int i = 1; i <= n; i++) ans[i] = inf;
//线段树初始化，dis是线段树，ans是答案
build(1, 1, n);
change(1, 1, n, S, 0); ans[S] = 0;
dij();
for(int i = 1; i <= n; i++) printf("%lld ", ans[i]);
return 0;
}
2.大佬的特殊线段树优化版本：（超快的）
此版本来源
先考虑一下如果要优化dijkstra算法，优先队列需要哪些操作，让线段树来实现它们。
查询队列是否为空，即还有没有要用来松弛其它点的点。
取出dist值最小的元素，并删除
修改一个点的dist值
如果我们用线段树来维护dist数组，那么修改操作就是非常简单的单点修改。
我们只要用线段树来维护区间dist最小元素是谁(minpos，简称mp)即可。
但是线段树是不支持删除元素的，我们可以把dist[0]设置为恒为inf，
如果要删除一个元素只要让它对应的叶节点mp值=0即可。
这样的话就会保证查询dist最小元素的时候一定不会查到它；
如果查到它就说明“优先队列”已经空了。
对比：
大佬的线段树版本：（超快的，内存超少的）
普通的线段树版本：（慢了一点）
堆（优先队列）优化版本：（好慢，占用内存还大）
#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])
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;
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> void write(T x) {
if (x < 0) x = -x, putchar('-');
if (x > 9) write(x / 10);
putchar(x % 10 + 48);
}
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);
erp(i, x) if (dist[v[i]] > dist[x] + w[i])
modify(v[i], dist[x] + w[i]);
}
}
int main() {
read(n),read(m),read(s);
rep(i, 1, m) {
int x, y, z; read(x),read(y),read(z); ae(x, y, z);
}
dijkstra(s);
rep(i, 1, n) write(dist[i]), putchar(' ');
puts("");
return 0;
}
二.SPFA 算法（可以处理存在负权的清况）
SPFA 算法详解(最短路径)
完整代码：
#include <bits/stdc++.h>
#define inf 0x3f3f3f3f
using namespace std;
const int M=10005;
struct A{
int y,time,next;
}a[M<<1];
int pre[M],cent=0;//链式前向星数组
int vis[M],ven[M],nums[M];
//SPFS数组，vis记录最短路，ven记录是否在队列，nums记录入队次数
void add(int x,int y,int k)//链式前向星，加入节点
{
a[cent].y=y, a[cent].time=k, a[cent].next=pre[x];
pre[x]=cent++;
}
bool SPFA(int s,int n)
{
queue <int> q;
memset(vis,inf,sizeof(vis));
memset(ven,0,sizeof(ven));
memset(nums,0,sizeof(nums));
vis[s]=0;//初始化距离
ven[s]=1,nums[s]++;//标记s节点在队列，队列次数+1
q.push(s);
while(!q.empty())
{
int x=q.front();
q.pop();//出队
ven[x]=0;//标记不在队列
for(int i=pre[x]; ~i; i=a[i].next)//遍历与x节点连通的点
{
int y=a[i].y;
if(vis[y]>vis[x]+a[i].time)//更新
{
vis[y]=vis[x]+a[i].time;
if(!ven[y])
//由于更新了节点，所以后续以这个为基础的最短路，也要更新下
//所以如果在队列就不用加入，不在的话加入更新后续节点
{
q.push(y);
ven[y]=1;//标记这个节点在队列中
nums[y]++;//记录加入次数
if(nums[y]>n)//如果这个点加入超过n次，说明存在负圈，直接返回
return false;
}
}
}
}
return true;
}
int main()
{
int n,m,t;
int b[M],c[M];
while(cin>>n>>m>>t)
{
cent=0;
memset(pre,-1,sizeof(pre));
for(int i=0;i<n;i++)
{
int x,y,k;
cin>>x>>y>>k;
add(x,y,k);
add(y,x,k);
}
for(int i=0;i<m;i++)
{
cin>>b[i];
}
for(int i=0;i<t;i++)
{
cin>>c[i];
}
int minn=inf;
for(int i=0;i<m;i++)//遍历多个找寻最小
{
SPFA(b[i],n);
for(int j=0;j<t;j++)
minn=min(minn,vis[c[j]]);
}
cout<<minn<<endl;
}
}
三.Floyd算法（可以处理存在负权的清况）
void Floyd()
{
for(int k = 1; k <= n; k++)//注意，一定要先枚举中转节点保证三角形的情况
for(int i = 1; i <= n; i++)
for(int j = 1; j <= n; j++)
dis[i][j] = min(dis[i][j], dis[i][k] + dis[k][j]);
}
1.P2888 [USACO07NOV]牛栏Cow Hurdles（Floyd算法）
P2888 [USACO07NOV]牛栏Cow Hurdles（Floyd算法）
四.路径还原
（1）模板
以下来自白书
如果需要输出路径
可以用一个prev[ j ]来记录最短路上顶点 j 的前驱，那么在o(|V|)的时间内完成最短路径的恢复。在d[ j ]被d[ j ] = d[ k ] + cost[ k ][ j ]更新时，修改prev[ j ] = k，这样就可以求出来prev的数组，可以在以上算法中用路径前驱标记法来还原出来路径。
这里给出dijkstra算法的路径还原算法代码：
int cost[MAX_V][MAX_V]; //cost[u][v]表示边e=(u, v)的权值（不存在这条边时设为INF）
int d[MAX_V]; //从顶点s出发的最短距离
bool used[MAX_V]; //已经使用过的图中的点
int V; //顶点数
int prev[MAX_V]; //记录前驱点
//从s出发到各个顶点的距离
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[u][v]); //因为加入了一个点V所以所有的d都要再更新一遍
prev[u] = v;
}
}
}
vector<int> get_path(int t) //到顶点t的最短路
{
vector<int> path;
for(; t != -1; t = prev[t])
path.push_back(t);
reverse(path.begin(), path.end());
return path;
}
（2）模板题
B. wzy的大冒险——出发咯QAQ
wzy踏上了冒险的旅程。
现在他从地精手里买了一份地图，地图上有n个城镇。
他从第一个城镇出发，走向（没钱只能走）第n个城镇，现在，请你帮wzy找到一条最短的路径，并倒序（从n到1）输出一条最短路径。
举个栗子:如果有两条路径6 4 3 1和6 5 2 1，我们选择6 4 3 1这条。
地精小提示：路是单向的QAQ。
输入格式
第一行两个数n,m ，(1≤n≤103,1≤m≤103)
接下来m行，每行三个数x,y,z，表示点 x 与点 y 之间有一条权值为 z 的有向边 (1≤x,y,z≤103).
输出格式
第一行一个整数表示 1 到 n 的最短距离；
第二行倒序输出这条路径。
样例
input
5 7
1 2 69
1 3 87
1 4 79
2 5 94
2 3 10
3 5 79
4 5 43
output
122
5 4 1
#include<bits/stdc++.h>
using namespace std;
#define debug(x) cout<<"# "<<x<<" "<<endl;
typedef int ll;
//const ll mod=2147483647000;
const ll N=1010;
const ll INF=0x7f7f7f7f;
//邻接矩阵存图
ll G[N][N],used[N],dis[N],pre[N],n,m;
inline void dijkstra(ll s)//s是起点
{
memset(used,0,sizeof(used));
memset(dis,0x7f,sizeof(dis));
memset(pre,-1,sizeof(pre));
dis[s]=0;
while(1)
{
ll v=-1;
for(int i=1;i<=n;++i)
if(!used[i]&&(v==-1||dis[i]<dis[v]))
v=i;
if(v==-1)break;
used[v]=1;
for(int i=1;i<=n;++i)
{
if(dis[i]>dis[v]+G[v][i])
{
dis[i]=dis[v]+G[v][i];
pre[i]=v; //保存最短路上下一个节点的前驱
}
}
}
}
vector<ll> get_graph(ll t)//此路径是逆序的
{
vector<ll> mp;
for(;t!=-1;t=pre[t])
mp.push_back(t);
//reverse(mp.begin(),mp.end());//需要正序就用reverse
return mp;
}
int main()
{
while(scanf("%d %d",&n,&m)!=EOF)
{
memset(G,INF,sizeof(G));//这样赋值必须是int型！
ll a,b,c;
for(int i=0;i<m;++i)
{
scanf("%d %d %d",&a,&b,&c);
G[a][b]=c;
}
dijkstra(1);
vector<ll>ans=get_graph(n);
int len=ans.size();
cout<<dis[n]<<endl;
for(int i=0;i<len;++i)
printf("%d%c",ans[i],i==len-1?'\n':' ');
}
return 0;
}
专题·最短路【including Dijkstra， SPFA，Floyd，传递闭包，二维最短路，分层图最短路，最短路计数……
注：如果您通过本文,有(qi)用(guai)的知识增加了，请您点个赞再离开,如果不嫌弃的话,点个关注再走吧 ! 当然，也欢迎在讨论区指出此文的不足处，作者会及时对文章加以修正 !
京公网安备 11010502036488号