526互联

浅谈最短路问题

发布时间 2024-01-11 19:58:33作者: 单南松

浅谈最短路

Part1. 前言

最短路基本原理在这里不多赘述，SPFA 和 dijkstra 原理没有记录，主要内容为全源最短路和单源最短路的各种应用。

Part2.最短路板子

//dijkstra
int idx, h[N], e[M], w[M], ne[M];
int dist[N];
bool v[N];

priority_queue<pair<int, int> > q;

void add(int a, int b, int c)
{
	e[++idx] = b, w[idx] = c, ne[idx] = h[a], h[a] = idx;
}

void dijkstra(int s)
{
	memset(dist, 0x3f, sizeof dist);
	memset(v, 0, sizeof v);
	dist[s] = 0;
	q.push(make_pair(0, s));
	while (!q.empty())
	{
		int x = q.top().second;
		q.pop();
		if(v[x]) continue; 
		v[x] = 1;
		for (rint i = h[x]; i; i = ne[i])
		{
			int y = e[i];
			int z = w[i];
			if (dist[y] > dist[x] + z)
			{ 
				dist[y] = dist[x] + z;
				q.push(make_pair(-dist[y], y));
			}
		}
	}
}

signed main()
{
	//输入
	dijkstra(s);
	for (rint i = 1; i <= n; i++) 	cout << dist[i] << " ";
	return 0;
}
//SPFA
int n, m, s;
int idx;
int h[N], e[M], ne[M], dist[N], w[M];

queue<int> q;
bool v[N];

void add(int a, int b, int c)
{
	e[++idx] = b, w[idx] = c, ne[idx] = h[a], h[a] = idx; 
}

void SPFA(int s)
{
	memset(dist, 0x3f, sizeof dist);
	memset(v, 0, sizeof v);
	dist[s] = 0;
	v[s] = 1;
	q.push(s);
	while(!q.empty())
	{
		int x = q.front();
		q.pop();
		v[x] = 0;
		for (rint i = h[x]; i; i = ne[i])
		{
			int y = e[i];
			int z = w[i];
			if (dist[y] > dist[x] + z)
			{
				dist[y] = dist[x] + z;
				if (!v[y]) q.push(y), v[y] = 1;
			}
		}
	}
}

signed main()
{
	SPFA(s);
	return 0;
}

Part3.全源最短路

Floyd

模板题传送门 B3647 【模板】Floyd

全源最短路，顾名思义，就是要求出所有点之间的最短路径。既然要求出所有点复杂度必然不会低。Floyd 是一种类似于 dp 的方法，dist[i][j] = min(dist[i][j], dist[i][k] + dist[k][j]) 进行转移。即可求出答案。

int n, m;
int dist[N][N];

void floyd()
{
    for (rint k = 1; k <= n; k++)
        for (rint i = 1; i <= n; i++)
            for (rint j = 1; j <= n; j++)
                dist[i][j] = min(dist[i][j], dist[i][k] + dist[k][j]);
}

signed main()
{
    cin >> n >> m;

    for (rint i = 1; i <= n; i++)
    {
        for (rint j = 1; j <= n; j++)
        {
            if (i == j) dist[i][j] = 0;
            else dist[i][j] = inf;              	  	
		}
	}

    while (m--)
    {
        int u, v, w;
        cin >> u >> v >> w;
        dist[u][v] = min(dist[u][v], w);
        dist[v][u] = min(dist[v][u], w);
    }

    floyd();

    for (rint i = 1; i <= n; i++)
    {
    	for (rint j = 1; j <= n; j++) cout << dist[i][j] << " ";
		cout << endl;
	}

    return 0;
}

Johnson

模板题传送门P5905 【模板】全源最短路

\(Dijkstra\) 不能处理负边。但是对于这个题偏偏又有。所以直接跑好几轮 \(Spfa\) ？找死。所以把每条边变成非负值。不能每条边同时加同一个数，这样答案就你不知道最后要减去几个你加的值。

所以，我们先跑一遍 \(Spfa\)，顺便记录一些信息，顺手判掉负环。

当我们跑 \(Spfa\) 时，我们可以先设一个虚拟点 \(0\)，这个点连上每一个点，边权为 \(0\)。以这个点位源点跑 \(Spfa\)，用 \(f\) 数组记录，即 \(0\) 到每个点的最短路，其实这个 f[i] 的作用就是原来的 dist[i]。接着，对于一条边 \(u,v,w_{u,v}\)。由三角形不等式 \(f_u+f_{u,v}≥f_v\) 得，\(w_{u,v}+f_u-f_v≥0\)。只需要将每条边的边权 \(w_{u,v}\) 加上 \((f_u-f_v)\) 即可满足非负。最终求出来的最短路 \(dist_{s,t}\) 减去 \((f_s-f_t)\) 即可。然后在记录答案用一个 vector 即可。

#include <bits/stdc++.h>

#define int long long
#define rint register int
#define endl '\n'

using namespace std;

const int N = 1e5 + 5;
const int M = 1e6 + 5;
const int inf = 1e9;

int n, m;
int idx, h[N], ne[M], e[M], w[M];
int dist[N], cnt[N];
bool v[N];
int f[N];
vector<int> ans;

void add(int a, int b, int c)
{
    e[++idx] = b, w[idx] = c, ne[idx] = h[a], h[a] = idx;
}

bool SPFA(int s)
{
	queue<int> q;
	for (rint i = 1; i <= n; i++) f[i] = inf;
    memset(v, 0, sizeof v); 
    f[s] = 0;
    v[s] = true;
    q.push(s);
    cnt[s] = 0;
    while (!q.empty())
    {
        int x = q.front();
        q.pop();
        v[x] = 0;
        for (rint i = h[x]; i; i = ne[i])
        {
            int y = e[i];
            int z = w[i];
            if (f[y] > f[x] + z)
            {
                f[y] = f[x] + z;
                cnt[y] = cnt[x] + 1;
                if (cnt[y] >= n + 1) return 0;
                if (!v[y])
                {
                    q.push(y);
                    v[y] = 0;
                }
            }
        }
    }
    return 1;
}

void dijkstra(int s)
{
	priority_queue<pair<int, int> > q;
	for (rint i = 1; i <= n; i++) dist[i] = inf;
	memset(v, 0, sizeof v);
	dist[s] = 0;
	q.push(make_pair(0, s));
	while (!q.empty())
	{
		int x = q.top().second;
		q.pop();
		if(v[x]) continue;
		v[x] = 1;
		for (rint i = h[x]; i; i = ne[i])
		{
			int y = e[i];
			int z = w[i];
			if (dist[y] > dist[x] + z)
			{ 
				dist[y] = dist[x] + z;
				q.push(make_pair(-dist[y], y));
			}
		}
	}
}

void build()
{
    cin >> n >> m;
    for (rint i = 1; i <= m; i++)
    {
		int a, b, c;
		cin >> a >> b >> c;
		add(a, b, c);
	}
	for (rint i = 1; i <= n; i++) add(0, i, 0);	
}

void check()
{
	if (!SPFA(0)) 
	{
		puts("-1");
		exit(0);
	}	
}

void calc_all_path()
{
	for (rint x = 1; x <= n; x++)
	{
		for (rint i = h[x]; i; i = ne[i])
		{
			int y = e[i];
			w[i] += f[x] - f[y];
		}
	}
	for (rint i = 1; i <= n; i++)
	{
		dijkstra(i);
		long long res = 0;
		for (rint j = 1; j <= n; j++)
		{
			if (dist[j] == inf) res += j * inf;
			else res += j * (dist[j] + f[j] - f[i]);
		}
		ans.push_back(res);
	}	
}

void print()
{
	for (rint i = 0; i < (int)ans.size(); i++)
	{
		cout << ans[i] << endl;
	}
}

signed main()
{
    build();
    check();
    calc_all_path();
    print();
    return 0;
}

Part4. K 短路

这种问题很麻烦，我们不妨先从次短路入手。

次短路

P2865 [USACO06NOV] Roadblocks G

我们只需要在原来 dijkstra 的模板上小改一手就可以了。

只需要再开 一个 need[] 来维护，如果 dist[y] <= x + z ，考虑 need[y] > x + z，更新答案即可。

void second_path_dijkstra()
{
    memset(dist, 0x3f, sizeof dist);
    memset(need, 0x3f, sizeof need);
	
    dist[s] = 0;
    q.push(make_pair(0, s));
    
    while (!q.empty())
    {
        int x = -q.top().first; 
	    int u = q.top().second;
        q.pop();
        
        for (rint i = h[u]; i; i = ne[i])
        {
            int y = e[i];
	        int z = w[i];
            if (dist[y] > x + z)
            {
                need[y] = dist[y]; 
                dist[y] = x + z;
                q.push(make_pair(-dist[y], y));
                q.push(make_pair(-need[y], y)); 
            }
            else if (need[y] > x + z)
            {
                need[y] = x + z; 
                q.push(make_pair(-need[y], y));
            }
        }
    }
}

signed main()
{
    cin >> n >> m;
    s = 1;

    for (rint i = 1; i <= m; i++)
    {
        int a, b, c;
        cin >> a >> b >> c;
        add(a, b, c);
        add(b, a, c);
    }

    second_path_dijkstra();

    cout << need[n] << endl;

    return 0;
}

K 短路

K 短路的求法求很多，普遍的是 \(A*\)，然后堆优化。但是一般来说，不可能再考到纯 K 短路板子题了，因为一道题如果与 K 短路联合考察，数据范围还卡的很死，这道题基本不可能有人场切了，现在的出题潮流也决定了不会这么出题。所以我们只需要搞出来一个相对复杂度不是很高能大概跑过 \(n<=10^3,m<=10^4\) 的算法就可以了。

本人不喜欢这么求 K 短路。更喜欢 dp 求 K 短路。

现在，\(n\) 个点 \(m\) 条边 \(k\) 短路。数据范围同上，如何用 dp 做呢？

设\(f[i][k]\)表示：以第 \(i\) 个点为终点的第 \(k\) 短路的长度。

将序列翻转，即从 \(1\) 号点出发，到达 \(n\) 号点。

对于一条路径 \((a,b,c)\) ，从 \(a\) 转移到 \(b\)。令一个辅助数组 \(g\) ，其中 \(g[k]=f[a][k]+c\)，即为从 \(a\) 点出发，到达\(y\)点的第 \(k\) 短的路的长度。因为 \(g[]\) 和 \(f[b]\) 都是递增的，直接归并。复杂度 \(O(mk)\)。

int n, m, q;
int f[N][M], g[M], h[M];
int s[M];
vector<pair<int, int> > v[M];

void calc_kth_path()
{
	for (rint i = 1; i <= n; i++)
	{
		for (auto j : v[i])
		{
			for (rint k = 1; k <= s[i]; k++) g[k] = f[i][k] + j.y;				
			merge(g + 1, g + s[i] + 1, f[j.x] + 1, f[j.x] + s[j.x] + 1, h + 1);
			s[j.x] = min(s[j.x] + s[i], q);
			for (rint k = 1; k <= s[j.x]; k++) f[j.x][k] = h[k];
		}
	}	
}

signed main()
{
	cin >> n >> m >> q;

	for (rint i = 1; i <= m; i++)
	{
		int a, b, c;
		cin >> a >> b >> c;
		v[b].push_back({a, c});
	}
	
	memset(f, 0x3f, sizeof f);
	f[1][1] = 0;
	s[1] = 1;
	
	calc_kth_path();
	
	for (rint i = 1; i <= q; i++)
	{
		cout << (f[n][i] >= inf ? -1 : f[n][i]) << endl;
	}
	
	return 0;
}