首页 > 其他分享 >Johnson 全源最短路

Johnson 全源最短路

时间:2023-10-02 22:33:25浏览次数:38  
标签:p1 Johnson int 全源 vis 复杂度 短路 define

Johnson 全源最短路

Johnson 和 Floyd 一样是能求出无负环图上任意两点间最短路径的算法。

引入

求任意两点间的最短路可以通过枚举起点,跑 \(n\) 次 SPFA 来解决,时间复杂度是 \(O(n^2 m)\) 的,也可以用 Floyd 解决,复杂度为 \(O(n^3)\)。

或者我们可以跑 \(n\) 次堆优化的 Dijkstra,复杂度为 \(O(nm\log m)\)。

但是 Dijkstra 有一个致命的缺陷就是他不能处理负边权。

我们不难想到来修改边权使其为正数。

核心思想

我们新建一个虚拟的节点,假设他的编号为 \(0\),从这个点向其他所有点连一条边权为 \(0\) 的边。

接下来我们跑一遍 SPFA,求出零号点到所有点的最短路记为 \(h_{i}\),顺便判断一下有没有负环。

如果存在一条边 \((u,v,w)\),我们将其修改为 \((u,v, w+h_{i}-h_{v})\)。

接下来以每一个点为起点跑 \(n\) 边 Dijkstra 就好了。

复杂度为 \(O(nm \log m)\)

正确性

我们考虑找到从 \(s\) 到 \(t\) 的一条路径为:

\[s\to p1 \to p2 \to \dots \to pk \to t \]

那么这条路径的长度就是:

\[(w(s,p1)+h_{s} - h_{p1}) + (w(p1,p2) + h_{p1}-h_{p2}) + \dots + (w(pk, t) + h_{pk} - h_{t}) \]

展开就是:

\[w(s, p1) + w(p1,p2) + \dots + w(pk,t) + h_{s} - h_{t} \]

所以无论怎么走,只要是 \(s\to t\) 的一条最短路径,那么最后就是比原答案多了 \(h_{s}-h_{t}\)。

Q:你说的对,但是为什么能保证修改后的边权都是非负数?

根据 \(h_{v}\le h_{u} + w(u,v)\),稍微变化一下就是 \(h_{u} + w(u,v) - h_{v} \ge 0\),所以图中的边权均为非负。

code

#include <bits/stdc++.h>

#define pii pair<int, int>
#define INF 1000000000
#define int long long
#define N 10010
#define endl '\n'

using namespace std;

inline int read()
{
    int x = 0, f = 1;
    char c = getchar();
    while(c < '0' || c > '9'){if(c == '-') f = -1; c = getchar();}
    while(c <= '9' && c >= '0') x = (x << 1) + (x << 3) + (c ^ 48), c = getchar();
    return x * f;
}

int n, m, t, head[N], vis[N], cnt[N], h[N], d[N], tot;
struct node{int v, next, w;}e[N << 4];

inline void add(int u, int v, int w){e[++ tot] = (node){v, head[u], w}; head[u] = tot;}

inline int spfa(int s)
{
	queue<int> q;
	memset(vis, 0, sizeof vis);
	for(int i = 1; i <= n; i ++) h[i] = INF;
	h[s] = 0;
	vis[s] = 1;
	q.push(s);
	while(!q.empty())
	{
		int u = q.front();
		q.pop();
		vis[u] = 0;
		for(int i = head[u]; i; i = e[i].next)
		{
			int v = e[i].v, w = e[i].w;
			if(h[v] > h[u] + w)
			{
				h[v] = h[u] + w;
				if(!vis[v])
				{
					vis[v] = 1;
					cnt[v] ++;
					q.push(v);
					if(cnt[v] == n + 1) return 0;
				}
			}
		}
	}
	return 1;
}

inline void dijkstra(int s)
{
	priority_queue<pii, vector<pii>, greater<pii> > q;
	memset(vis, 0, sizeof vis);
	for(int i = 1; i <= n; i ++)d[i] = INF;
	d[s] = 0;
	q.push({0, s});
	while(!q.empty())
	{
		int u = q.top().second;
		q.pop();
		if(vis[u]) continue ;
		vis[u] = 1;
		for(int i = head[u]; i; i = e[i].next)
		{
			int v = e[i].v, w = e[i].w;
			if(d[v] <= d[u] + w) continue;
			d[v] = d[u] + w;
			q.push({d[v], v});
		}
	}
    return ;
}

signed main()
{
	n = read(), m = read();
	for(int i = 1; i <= n; i ++) add(0, i, 0);
	for(int i = 1; i <= m; i ++)
	{
		int u = read(), v = read(), w = read();
		add(u, v, w);
	}
	if(!spfa(0)) return cout << "-1" << endl, 0;//负环输出0
	for(int u = 1; u <= n; u ++)
		for(int i = head[u]; i; i = e[i].next)
			e[i].w += h[u] - h[e[i].v];//修改边权
	for(int i = 1; i <= n; i ++)
	{
		dijkstra(i);
		int ans = 0;
		for(int j = 1; j <= n; j ++)
        {
			if(d[j] == INF) ans += j * INF;
			else ans += j * (d[j] + h[j] - h[i]);
        }
		cout << ans << endl;
	}
	return 0;
}

参考文章:https://zhuanlan.zhihu.com/p/99802850

标签:p1,Johnson,int,全源,vis,复杂度,短路,define
From: https://www.cnblogs.com/Multitree/p/17740532.html

相关文章

  • P1144 最短路计数 题解
    Problem考察算法:拓扑排序+\(DP\)+\(Dijkstra\)。题目简述给出一个无向无权图,问从顶点\(1\)开始,到其他每个点的最短路有几条。思路先求出\(1\)号点到每个点的最短路\(d_i\)。分析每条边$(x,y)$:如果d[x]+1==d[y]:这条边有用。将所有有用的边拓扑排序......
  • 853. 有边数限制的最短路
    第一版err#include<iostream>#include<cstdio>#include<cstring>#include<algorithm>#include<queue>#include<cmath>#defineN505usingnamespacestd;intn,m,k,dis[N],cnt,hd[N],vis[N],x,y,z;structEdge{intto,nxt......
  • 单源最短路模板
    SPFA#include<bits/stdc++.h>#definerintregisterint#defineendl'\n'usingnamespacestd;constintN=1e5+5;constintM=1e6+5;constintinf=1e9;inth[N],e[M],ne[M],dist[N],w[M];intn,m,s,idx;queue<int>......
  • [算法分析与设计] 1. 全源最短路近似
    全源最短路(APSP)近似。有两种近似stretch\(k\).\(\delta(u,v)\leqd(u,v)\leqk\cdot\delta(u,v)\).surplus\(t\).\(\delta(u,v)\leqd(u,v)\leq\delta(u,v)+t\).其中,\(\delta(u,v)\)表示\(u,v\)间真实的最短路长度。先来考虑无权图上的surplus......
  • 最短路与次短路
    最短路算法不再赘述,假定我们已经求出了最短路,记\(f[x,y]\)为\(x\)到\(y\)的最短路。记\(g[x,y]\)为\(x\)到\(y\)的严格次短路。最短路树的定义单源最短路问题中,如果p1->p2->p3->...pn是一条最短路,就将它的边都加入图中。将所有的最短路径都这样处理,得到的图就......
  • P7916 [CSP-S 2021] 交通规划 sol-最短路+环形dp
    P7916[CSP-S2021]交通规划solStatement传送门Solution好题。发现\(k\le2\)的分值非常多,于是我们考虑从\(k=2\)入手。颜色相同就不用说了,直接染成同一种颜色就行了。我们考虑其他情况,就是颜色不相同的情况,我们一定是找了一条路径把这个图给切开了就像这个样子。......
  • 最短路基础实现方法模板合集
    $\color{#39c588}{关于最短路}$$\color{purple}{首先是最短路的算法选择思路捏,直接来个Y总的图}$++$\color{purple}{单源汇问题}$++$\color{orange}{朴素版Dijkstra}$实现思路//朴素版Dijkstrao(n^2)--处理稠密图--稠密图用邻接矩阵存储//1.初始化邻接......
  • 同余最短路
    简述:完全背包,但物品质量很大(105左右),空间上第二维开不下,时间上狠狠超时,咋办呐,同余最短路咯(不小心学到的)  先简写f[(i+aj)%m]=min( f[(i+aj)%m],f[i]+aj)类比最短路Dijkstra咋求的d[y]=min(d[y],d[x]+vx,y)sox->i,y->(i+aj)%m,x->y建一条有向边,最......
  • 最短路之Floyd(医院设置)
    题意题目链接:https://www.luogu.com.cn/problem/P1364给一个二叉树,每个结点有一个值,这个值代表这个结点(即城市)有多少人,然后需要在这些结点中选出一个结点作为医院,问选哪个结点得到的距离和最小。距离和为人数乘以路径长度。思路用最短路,就是先求出每两个点之间的最短......
  • 20-布尔值-比较运算符-逻辑运算符-短路问题
            ......