最短路径树
XyzL
2020-10-05 19:38:06
## 前置知识：
1: **单源最短路径算法**
## 何为最短路径树？
所谓最短路径树 $(Shortest Path Tree)$ ，简称 $SPT$ ，就是从一张**连通**图中，有树满足从根节点到任意点的路径都为**原图中根到任意点的最短路径**的树。
可能描述的有点繁琐，如果看不懂可以观看一下[百度百科](https://baike.baidu.com/item/%E6%9C%80%E7%9F%AD%E8%B7%AF%E5%BE%84%E6%A0%91/22787159)给出的定义：
考虑一个连通无向图 $G$ ，一个以顶点 $v$ 为根节点的最短路径树 $T$ 是图 $G$ ，满足下列条件的生成树——树 $T$ 中从根节点 $v$ 到其它顶点 $u$ 的路径距离，在图 $G$ 中是从 $v$ 到 $u$ 的最短路径距离。
1 最短路径树是一棵生成树，保证每一个点**联通**。
2 从**根节点**在这棵树上的任意点路径 $=$ **原图**两点之间的最短路径，即任意点 $i$ 都有 $len_i$ $=$ $dis_i$。
## 最短路径树×最小生成树的区别？
最小生成树只是满足全图联通且**边权集**最小，而最短路径树是满足从根节点到任意点的最短路。
更直观的显示如下：
**原图：**
**最短路径树：**
**最小生成树：**
最短路径树的边权和为 $75$ ，最小生成树的边权和为 $67$ 。
另外的，最短路径树的边权和 $≥$ 最小生成树的边权和。
## 如何得出最短路径树？
根据定义，最短路径树是从根节点到任一点的路径都为**最短路**，由此我们可以想到**单源最短路径算法**，常用的单源最短路径算法有 $Dijkstra$ 和 $Bellman-Ford$ ，这里我们使用 $Dijkstra$ 。
$Dijkstra$ 算法是往一个集合不断往里面加入**新的节点**，通过**松弛操作**从而得到从**其它节点**出发到所有节点的最短路径。
代码如下：
```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 ;
}
```
我们在进行该算法，对于每一个节点都是由一条边拉进来的，当前存入 $dis$ 这个集合，每次进行松弛的时候都会将一个**新点**拉入集合，这样从根节点 $($ 源点 $)$ 可以形成树。因为在树中**一个点就可以对应一条边**，我们可以使用一个数组 $pre$ 来记录点 $i$ 的**前驱**，即从源点到点 $i$ 的**上一条边的编号**。
Tip: 这里 $pre$ 记录是**边的编号**而不是点的编号。
而很多时候，我们需要保证树上所有的**边权和最小**，所以我们可以采用一个**贪心**的思想，进行松弛的时候如果**松弛前的结果**与**松弛后的结果**相等即 $dis[now] = dis[next] + w$，我们可以比较两种情况时，**连接这条点的边的大小**，即 $w[i]$ 与 $w[pre[next]]$ ，如果$w[i] < w[pre[next]]$ ，那么我们更新当前的 $pre$ 。
```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](https://www.luogu.com.cn/problem/CF545E)
### 题意：
给定一张带边权的联通无向图 $G$ ，有 $n(1≤n≤300000)$ 个点和 $m$ 条边，再给定一个顶点 $u$ ，求此图中**边权和最小**的 $SPT$ ，输出该树权值和和和每条**边的编号**。
### 分析：
如果我们一开始没有接触过**最短路径树**，那么对于这道题我们很容易想到**最小生成树**，而这种方法上面已经说明是错的。
不考虑正解的前提下，我们还有一种**暴力**的方法，使用 $Dijkstra$ 找出权值和最小的最短路径树的**权值和**，然后再暴力枚举，选一条边，**如果把这条边删掉，对最小花费有影响，说明这个肯定是最短路径树上的边**，此算法权值和为 $O((n \log_2 n)^2)$ 。
**正解**前文已上述，由于答案还要输出构成该树的边的编号，由于我们采用**链式前向星**建的双向边，所以原题中所有边的编号都存了两次，根据 $int$ 除法**向下取整**的特性，我们只需对编号 $pre + 1$ $/2$。
综上，时间复杂度为 $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](https://www.luogu.com.cn/problem/CF1076D)
### 题意：
给定一个 $n(1≤n≤300000)$ 个点,$m(1≤m≤300000)$条边的无向简单带权连通图, 要求删边至最多剩余 $k$ 条边。
定义**好点**是指删边后, 1号节点到它的最短路长度仍然等于原图最短路长度的节点。
最大化删边后的好点个数。
### 分析：
通过上述知识，我们可以发现好点的定义就是**最短路径树**上的点，所以我们只需要将1号节点当做根节点，使用 $DFS$ 从其出发进行遍历 $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](https://www.luogu.com.cn/problem/CF1005F)
### 题意：
给定一个 $n(1≤n≤200000)$ 个点,$m(1≤m≤200000)$条边的无向简单连通图，每条边权为 $1$ ，求最短路径树的方案数，并输出每种方案
### 分析：
通过上述知识，我们可以知道这是个最短路计数问题，由于每个边的边权为 $1$ ，所以我们求最短路径树的时候可以要将**最短路退化成广搜**。
对于方案，我们可以在加边记录边的编号，然后对每个点维护一个能转移其的最短路的边的**编号集**，这样总的方案数就是**所有集合大小的乘积**，然后用 $DFS$ 在每个集合中选一个元素输出。
### 代码：
```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：最短路径树与最小生成树算法 $Kruskal$ 和 $Prim$ 无关。
2：最短路径树是采用**单源最短路径算法**来实现的。
3：注意记录该算法**点与边**的关系。
向先知先觉的 $Dijkstra$ 老爷子致敬！
