专栏文章

最短路径树

XXyzL
算法·理论参与者 34已保存评论 36

文章操作

快速查看文章及其快照的属性，并进行相关操作。

当前评论
36 条
当前快照
1 份
快照标识符
@mhz5u00g
此快照首次捕获于
2025/11/15 01:57
3 个月前
此快照最后确认于
2025/11/29 05:25
3 个月前
查看原文

前置知识：

1: 单源最短路径算法

何为最短路径树？

所谓最短路径树 (ShortestPathTree)(Shortest Path Tree) ，简称 SPTSPT ，就是从一张连通图中，有树满足从根节点到任意点的路径都为原图中根到任意点的最短路径的树。
可能描述的有点繁琐，如果看不懂可以观看一下百度百科给出的定义：
考虑一个连通无向图 GG ，一个以顶点 vv 为根节点的最短路径树 TT 是图 GG ，满足下列条件的生成树——树 TT 中从根节点 vv 到其它顶点 uu 的路径距离，在图 GG 中是从 vv 到 uu 的最短路径距离。
1 最短路径树是一棵生成树，保证每一个点联通。
2 从根节点在这棵树上的任意点路径 == 原图两点之间的最短路径，即任意点 ii 都有 lenilen_i == disidis_i。

最短路径树×最小生成树的区别？

最小生成树只是满足全图联通且边权集最小，而最短路径树是满足从根节点到任意点的最短路。
更直观的显示如下：
原图：原图
最短路径树：最短路径树
最小生成树：最小生成树
最短路径树的边权和为 7575 ，最小生成树的边权和为 6767 。
另外的，最短路径树的边权和 ≥≥ 最小生成树的边权和。

如何得出最短路径树？

根据定义，最短路径树是从根节点到任一点的路径都为最短路，由此我们可以想到单源最短路径算法，常用的单源最短路径算法有 DijkstraDijkstra 和 Bellman−FordBellman-Ford ，这里我们使用 DijkstraDijkstra 。
DijkstraDijkstra 算法是往一个集合不断往里面加入新的节点，通过松弛操作从而得到从其它节点出发到所有节点的最短路径。
代码如下：
CPP
void Dijskra(int start) { // 源点 

	priority_queue <Node> pq; // 优先队列维护当前全职最小 
	for(register int i = 1; i <= n; ++i) {
		dis[i] = INF; // DP初始化 
	}
	
	dis[start] = 0; // DP的边界条件 
	node Start = {start, 0};
	pq.push(Start); // 确定源点到源点的最短路径 将源点放入优先队列进行广搜 
	
	while(!pq.empty()) {
		node u = pq.top(); // 中转点
		pq.pop();
		int x = u.id, w = u.dist;
		if(vis[u]) {
			continue; // 防止多次将一个点加入堆中 
		}
		vis[u] = true;
		for(register int i = head[u]; i; i = edges[i].next) { // 找邻居 
            int next = edges[i].to, w = edges[i].w;
            if(dis[next] - dis[u] > w) { // 松弛操作 
                dis[next] = dis[u] + w;
                Node nxt = {next, dis[next]}; 
                pq.push(nxt);
            }
		}
	}
	
	return ;
}
我们在进行该算法，对于每一个节点都是由一条边拉进来的，当前存入 disdis 这个集合，每次进行松弛的时候都会将一个新点拉入集合，这样从根节点 (( 源点 )) 可以形成树。因为在树中一个点就可以对应一条边，我们可以使用一个数组 prepre 来记录点 ii 的前驱，即从源点到点 ii 的上一条边的编号。
Tip: 这里 prepre 记录是边的编号而不是点的编号。
而很多时候，我们需要保证树上所有的边权和最小，所以我们可以采用一个贪心的思想，进行松弛的时候如果松弛前的结果与松弛后的结果相等即 dis[now]=dis[next]+wdis[now] = dis[next] + w，我们可以比较两种情况时，连接这条点的边的大小，即 w[i]w[i] 与 w[pre[next]]w[pre[next]] ，如果w[i]<w[pre[next]]w[i] < w[pre[next]] ，那么我们更新当前的 prepre 。
CPP
for(register int i = head[u]; i != 0; i = edges[i].next) { // 找邻居 
    int next = edges[i].to, w = edges[i].w;
    if(dis[next] - dis[u] > w) { // 松弛操作 
        dis[next] = dis[u] + w;
        Node nxt = {next, dis[next]}; 
        pq.push(nxt);
        pre[next] = i;
    }
    if(dis[next] == dis[u] + edges[i].w && edges[i].w < edges[pre[next]].w) { // 松弛前后相等，比较前驱 
    	pre[next] = i;
	}
}

如何应用？

CF545E Paths and Trees

题意：

给定一张带边权的联通无向图 GG ，有 n(1≤n≤300000)n(1≤n≤300000) 个点和 mm 条边，再给定一个顶点 uu ，求此图中边权和最小的 SPTSPT ，输出该树权值和和和每条边的编号。

分析：

如果我们一开始没有接触过最短路径树，那么对于这道题我们很容易想到最小生成树，而这种方法上面已经说明是错的。
不考虑正解的前提下，我们还有一种暴力的方法，使用 DijkstraDijkstra 找出权值和最小的最短路径树的权值和，然后再暴力枚举，选一条边，如果把这条边删掉，对最小花费有影响，说明这个肯定是最短路径树上的边，此算法权值和为 O((nlog⁡2n)2)O((n \log_2 n)^2) 。
正解前文已上述，由于答案还要输出构成该树的边的编号，由于我们采用链式前向星建的双向边，所以原题中所有边的编号都存了两次，根据 intint 除法向下取整的特性，我们只需对编号 pre+1pre + 1 /2/2。
综上，时间复杂度为 O((n+m)log⁡2n)O((n + m) \log_2 n) 。

代码：

CPP
#include<bits/stdc++.h>

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;
}

const long long INF = 0x3f3f3f3f3f3f3f3f;
const int Maxn = 3e5 + 5;
const int Maxm = 6e5 + 5;

int n, m, s, cnt = 0, head[Maxn], pre[Maxn];

long long dis[Maxn], ans[Maxn];

bool vis[Maxn];

struct Line { // to指向的点， w是边权， next是这一条边连接的下一条边是谁
	int to;
	int w;
	long long next;
} edges[Maxm]; // 存所有的边 

inline void Add(int a, int b, long long w) { // 添加边的函数
	++cnt; // 边的编号 
	edges[cnt].to = b; // 第cnt条边指向点y 
	edges[cnt].w = w; // 第cnt条边的权值 
	edges[cnt].next = head[a]; // 第cnt条边的指向连接点x的第一条边 
	head[a] = cnt; // 将连接点x的第一条边更新为第cnt条边
	return ;
}

struct Node {
	int id;
	long long dist;
	bool operator < (const Node &cur) const {
		return dist > cur.dist;
	}
} ;

inline void Dijkstra(int start) {
	priority_queue <Node> pq; // 优先队列维护当前权值最小 
	for(register int i = 1; i <= n; ++i) {
		dis[i] = INF; // DP初始化 
		vis[i] = false;
	}
	dis[start] = 0; // DP的边界条件 
	Node Start = {s, 0};
	pq.push(Start); // 确定源点到源点的最短路径 将源点放入优先队列进行广搜 
	while(!pq.empty()) {
		Node now = pq.top();
		pq.pop();
		int u = now.id; // 中转点
		if(vis[u] == true) {
			continue; // 防止多次将一个点加入堆中 
		}
		vis[u] = true;
		for(register int i = head[u]; i != 0; i = edges[i].next) { // 找邻居 
            int next = edges[i].to;
			long long w = edges[i].w;
            if(dis[next] > dis[u] + w) { // 松弛操作 
                dis[next] = dis[u] + w;
                Node nxt = {next, dis[next]}; 
                pq.push(nxt);
                pre[next] = i;
            }
            if(dis[next] == dis[u] + edges[i].w && edges[i].w < edges[pre[next]].w) {
            	pre[next] = i;
			}
		}
	}
	return ;
}

signed main() {
	n = read(), m = read();
	for(register int i = 1; i <= m; ++i) { // m条边
		int x = read(), y = read();
		long long w = read();
		Add(x, y, w), Add(y, x, w); // 双向边 
	}
	s = read();
	Dijkstra(s);
	long long sum = 0, tot = 0;
	for(register int i = 1; i <= n; ++i) {
		if(i == s) {
			continue; // 源点到自己无边
		}
		int id = pre[i];
		long long w = edges[id].w;
		sum += w;
		ans[++tot] = id; // 记录边的编号
	}
	sort(ans + 1, ans + tot + 1);
	printf("%lld\n", sum);
	for(register int i = 1; i <= tot; ++i) { // 向下取整
		printf("%lld ", (ans[i] + 1) / 2);
	}
	puts("");
	return 0;
}
CF1076D Edge Deletion

题意：

给定一个 n(1≤n≤300000)n(1≤n≤300000) 个点,m(1≤m≤300000)m(1≤m≤300000)条边的无向简单带权连通图, 要求删边至最多剩余 kk 条边。
定义好点是指删边后, 1号节点到它的最短路长度仍然等于原图最短路长度的节点。
最大化删边后的好点个数。

分析：

通过上述知识，我们可以发现好点的定义就是最短路径树上的点，所以我们只需要将1号节点当做根节点，使用 DFSDFS 从其出发进行遍历 min(n,k+1)min(n, k + 1) 个节点，就可以保证图联通了。

代码：

CPP
#include<bits/stdc++.h>

using namespace std;

#define int long long // 坏习惯...

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;
}

const int INF = 0x3f3f3f3f3f3f3f3f;
const int Maxn = 3e5 + 5;
const int Maxm = 6e5 + 5;

int n, m, s, k, cnt, sum, head[Maxn], dis[Maxn], pre[Maxn];

bool vis[Maxn], ins[Maxm];

struct Line {
	int to;
	int w;
	int next;
} edges[Maxm];

inline void Add(int a, int b, int w) {
	++cnt;
	edges[cnt].to = b;
	edges[cnt].w = w;
	edges[cnt].next = head[a];
	head[a] = cnt;
	return ;
}

struct Node {
	int id;
	int dist;
	inline bool operator < (const Node &cur) const {
		return dist > cur.dist;
	}
} ;

void Dijkstra(int start) {
	priority_queue <Node> pq;
	for(register int i = 1; i <= n; ++i) {
		dis[i] = INF;
		vis[i] = false;
	}
	dis[start] = 0;
	Node Start = {start, 0};
	pq.push(Start);
	while(!pq.empty()) {
		Node now = pq.top();
		pq.pop();
		int u = now.id;
		if(vis[u] == true) {
			continue;
		}
		vis[u] = true;
		for(register int i = head[u]; i != 0; i = edges[i].next) {
			int next = edges[i].to, w = edges[i].w;
            if(dis[next] - dis[u] > w) {
                dis[next] = dis[u] + w;
                Node nxt = {next, dis[next]};
                pq.push(nxt);
                pre[next] = i;
            }
            if(dis[next] == dis[u] + edges[i].w && edges[i].w < edges[pre[next]].w) {
            	pre[next] = i;
			}
		}
	}
	for(register int i = 1; i <= n; ++i) {
		vis[i] = false;
	}	
	return ;
}

void DFS(int x, int father) {
	if(sum == k) {
		puts("");
		exit(0);
	}
	for(register int i = head[x]; i != 0; i = edges[i].next) {
		int next = edges[i].to, w = edges[i].w;
		if(next == father) {
			continue;
		}
		if(pre[next] == i) {
			++sum;
			vis[next] = true;
			printf("%d ", (i + 1) / 2);
			DFS(next, x);
		}
	}
	return ;	
}

signed main() {
	n = read(), m = read(), k = read();
	for(register int i = 1; i <= m; ++i) {
		int a = read(), b = read(), w = read();
		Add(a, b, w), Add(b, a, w);
	}
	Dijkstra(1);
	printf("%lld\n", min(n - 1, k));
	DFS(1, 0); // 遍历节点，建树输出 
	return 0;
}
CF1005F Berland and the Shortest Paths

题意：

给定一个 n(1≤n≤200000)n(1≤n≤200000) 个点,m(1≤m≤200000)m(1≤m≤200000)条边的无向简单连通图，每条边权为 11 ，求最短路径树的方案数，并输出每种方案

分析：

通过上述知识，我们可以知道这是个最短路计数问题，由于每个边的边权为 11 ，所以我们求最短路径树的时候可以要将最短路退化成广搜。
对于方案，我们可以在加边记录边的编号，然后对每个点维护一个能转移其的最短路的边的编号集，这样总的方案数就是所有集合大小的乘积，然后用 DFSDFS 在每个集合中选一个元素输出。

代码：

CPP
#include<bits/stdc++.h>

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;
}

const int Maxn = 3e5 + 5;
const int Maxm = 6e5 + 5;

int n, m, s, k, cnt, sum, tot = 1, head[Maxn], dis[Maxn], pre[Maxn];

bool vis[Maxn];

struct Line {
	int to;
	int next;
	int num;
} edges[Maxm];

inline void Add(int a, int b, int w) {
	++cnt;
	edges[cnt].to = b;
	edges[cnt].next = head[a];
	edges[cnt].num = w;
	head[a] = cnt;
	return ;
}

vector <int> v[Maxn];

void BFS(int start) {
	queue <int> q;
	q.push(start);
	dis[start] = 0;
	while(!q.empty()) {
		int u = q.front();
		q.pop();
		for(register int i = head[u]; i != 0; i = edges[i].next) {
			int next = edges[i].to, num = edges[i].num;
			if(!dis[next]) {
				dis[next] = dis[u] + 1;
				v[next].push_back(num);
				q.push(next); 
			} else if(dis[next] == dis[u] + 1) {
				v[next].push_back(num);
			}
		}
	}
	return ;
}

void DFS(int x) {
	if(x == n + 1) {
		for(register int i = 1; i <= m; ++i) {
			printf("%d", vis[i]);
		}
		puts("");
		sum++;
		if(sum == tot) {
			exit(0); 
		}
		return ;
	}
	for(register int i = 0; i < v[x].size(); ++i) {
        vis[v[x][i]] = 1;
        DFS(x + 1);
        vis[v[x][i]] = 0;	
	}
	return ;
}

signed main() {
	n = read(), m = read(), k = read();
	for(register int i = 1; i <= m; ++i) {
		int x = read(), y = read();
		Add(x, y, i), Add(y, x, i);
	}
	BFS(1);
	for(register int i = 2; i <= n; ++i) {
		if(tot * v[i].size() > k) {
			tot = k;
			break;
		} else {
			tot *= v[i].size();
		}
	}
	printf("%d\n", tot);
	DFS(2);
	return 0;
}

总结：

1：最短路径树与最小生成树算法 KruskalKruskal 和 PrimPrim 无关。
2：最短路径树是采用单源最短路径算法来实现的。
3：注意记录该算法点与边的关系。
向先知先觉的 DijkstraDijkstra 老爷子致敬！
老爷子

评论

共 36 条评论，欢迎与作者交流。

正在加载评论...