浅谈最短路树 & 最短路图

· · 算法·理论

介绍

最短路树 & 最短路图是解决单源最短路进阶问题的重要工具。众所周知，在 Dijkstra 过程中有一个松弛操作：

if (dis[v] > dis[u] + w) {
  dis[v] = dis[u] + w;
}

在不含零环的图上，如果把发生了松弛的边单独拿出来，就会构成一个 DAG，这个图就叫最短路图。而如果给一个更强的条件，比如从源点到每个点的最短路唯一，建出来就是一棵树，叫做最短路树。

在最短路不唯一的图上，我们也可以建最短路树，但这时建立的最短路树不唯一。使用二叉堆优化的 Dijkstra 建最短路图 / 树，复杂度为 O(m \log n)。

根据定义，我们可以发现这样两条性质：

  1. 最短路树是一棵有根叶向树。
  2. 最短路树是最短路图的生成树。

下面我们通过一些例题来讲解最短路树 & 最短路图的应用。

例题

P2505 [HAOI2012] 道路

点的最短路计数是简单的，但是边的最短路计数不太好做。我们建立最短路图，这样从 s 到 t 的任意路径都是最短路，并且 DAG 上是可以 dp 的。

我们考虑把边的贡献化到点上，对于边 (u,v) 为最短路的次数即为起点到 u 的次数加上 v 到各个点的最短路个数。然后我们拓扑序上跑 dp，但是这里的转移顺序应当是拓扑反序。根据乘法原理，我们把 dp_u 乘上 dp_v 即为该边的答案。

::::info[代码]

const int N = 5005;
const long long mod = 1e9 + 7;
inline long long madd(long long a, long long b) {return a + b >= mod ? a + b - mod : a + b;}

int tot, head[N];
struct Edge {
    int from, next, to, dis;
} edge[N << 1];
inline void add_edge(int u, int v, int w) {
    edge[++tot].next = head[u], edge[tot].from = u, edge[tot].to = v, edge[tot].dis = w, head[u] = tot;
}
int dis[N];
long long cnt[N], dp[N], ecnt[N];
struct node {
    int to, dis;
    node() : to(0), dis(0) {}
    node(int v, int w) : to(v), dis(w) {}
    bool operator< (const node& a) const {return a.dis < dis;}
};

void dijkstra(int s) {
    priority_queue<node> q;
    memset(dis, 0x3f, sizeof(dis)), memset(cnt, 0, sizeof(cnt));
    dis[s] = 0, cnt[s] = 1, q.emplace(s, 0);
    stack<int> st;
    while (!q.empty()) {
        int u = q.top().to, d = q.top().dis; q.pop();
        if (dis[u] != d) continue;
        st.emplace(u);
        for (int j = head[u]; j != 0; j = edge[j].next) {
            int v = edge[j].to, w = edge[j].dis;
            if (dis[v] > dis[u] + w) {  
                dis[v] = dis[u] + w, cnt[v] = cnt[u];
                q.emplace(v, dis[v]);
            } else if (dis[v] == dis[u] + w) {
                cnt[v] = madd(cnt[u], cnt[v]);
            }
        }
    }
    while (!st.empty()) {
        int u = st.top(); st.pop();
        dp[u] = 1;
        for (int j = head[u]; j != 0; j = edge[j].next) {
            int v = edge[j].to, w = edge[j].dis;
            if (dis[v] == dis[u] + w) {
                ecnt[j] = madd(ecnt[j], cnt[u] * dp[v] % mod);
                dp[u] = madd(dp[u], dp[v]);
            }
        }
    }
}

int n, m, u, v, w;

void _main() {
    cin >> n >> m;
    for (int i = 1; i <= m; i++) {
        cin >> u >> v >> w;
        add_edge(u, v, w); 
    }
    for (int i = 1; i <= n; i++) dijkstra(i);
    for (int i = 1; i <= m; i++) cout << ecnt[i] << '\n';
}

::::

P2934 [USACO09JAN] Safe Travel G

最短路唯一，于是建立以 1 为根的最短路树，于是问题就是求不经过 (fa_i,i) 这条边时 1 到 i 的最短路，于是新的最短路就是从 1 到 x 再到 y 再到 i，其中 x 不在 i 子树中，而 y 在 i 的子树中。

发现非树边是关键的。枚举非树边 (u,v,w)，则贡献即为 dis_u+dis_v+w，对 u 到 v 的路径做一个区间最值操作，当然 \operatorname{lca}(u,v) 不行，因为这个点是断向根的边，而不是向儿子的边。

对于一条非树边 (u,v,w)，u,v 之间树上路径的长度不超过 w，不然这个树肯定不能是最短路树，因而 u,v 链的边数不超过 w，于是总复杂度是 O(mV)，V 为边权的值域，可以 AC，甚至连树剖都不用打暴力跳即可。

::::info[代码]

const int N = 1e5 + 5;
int tot = 1, head[N];
struct Edge {
    int next, from, to, dis;
} edge[N << 2];
inline void add_edge(int u, int v, int w) {
    edge[++tot].next = head[u], edge[tot].from = u, edge[tot].to = v, edge[tot].dis = w, head[u] = tot;
}
bool ontree[N << 2];

int dis[N];
struct node {
    int to, dis;
    node() : to(0), dis(0) {}
    node(int v, int w) : to(v), dis(w) {}
    bool operator< (const node& a) const {return a.dis < dis;}
};

void dijkstra(int s) {
    priority_queue<node> q;
    memset(dis, 0x3f, sizeof(dis));
    dis[s] = 0, q.emplace(s, 0);
    stack<int> st;
    while (!q.empty()) {
        int u = q.top().to; long long d = q.top().dis; q.pop();
        if (dis[u] != d) continue;
        st.emplace(u);
        for (int j = head[u]; j != 0; j = edge[j].next) {
            int v = edge[j].to; long long w = edge[j].dis;
            if (dis[v] > dis[u] + w) {  
                dis[v] = dis[u] + w;
                q.emplace(v, dis[v]);
            } 
        }
    }
    while (!st.empty()) {
        int u = st.top(); st.pop();
        for (int j = head[u]; j != 0; j = edge[j].next) {
            int v = edge[j].to; long long w = edge[j].dis;
            if (dis[v] == dis[u] + w) ontree[j] = ontree[j ^ 1] = true;
        }
    }
}

int dep[N], sz[N], fa[N], son[N], top[N], cnt, dfn[N];
void dfs1(int u, int f) {
    sz[u] = 1, fa[u] = f;
    for (int j = head[u]; j != 0; j = edge[j].next) {
        if (!ontree[j]) continue;
        int v = edge[j].to;
        if (v == f) continue;
        dep[v] = dep[u] + 1, dfs1(v, u), sz[u] += sz[v];
        if (sz[v] > sz[son[u]]) son[u] = v;
    }
}
void dfs2(int u, int t) {
    dfn[u] = ++cnt, top[u] = t;
    if (son[u]) dfs2(son[u], t);
    for (int j = head[u]; j != 0; j = edge[j].next) {
        if (!ontree[j]) continue;
        int v = edge[j].to;
        if (v != fa[u] && v != son[u]) dfs2(v, v);
    }
}

int lca(int u, int v) {
    while (top[u] != top[v]) {
        if (dep[top[u]] < dep[top[v]]) swap(u, v);
        u = fa[top[u]];
    }
    return dep[u] < dep[v] ? u : v;
}

struct segtree {
#define ls (rt << 1)
#define rs (rt << 1 | 1)
    int a[N];
    void build() {memset(a, 0x3f, sizeof(a));}
    void update(int l, int r, int c) {
        //debug(l), debug(r), debug(c);
        for (int i = l; i <= r; i++) a[i] = min(a[i], c);
    }
    void change(int x, int c) {a[x] = c;}
    long long query(int i) {return a[i];}
} sgt;

int n, m, u, v, w;
void change(int u, int v, int c) {
    while (top[u] != top[v]) {
        if (dep[top[u]] < dep[top[v]]) swap(u, v);
        sgt.update(dfn[top[u]], dfn[u], c);
        u = fa[top[u]];
    }
    if (dfn[u] > dfn[v]) swap(u, v);
    sgt.update(dfn[u], dfn[v], c);
}

void _main() {
    cin >> n >> m;
    for (int i = 1; i <= m; i++) {
        cin >> u >> v >> w;
        add_edge(u, v, w), add_edge(v, u, w);
    }
    dijkstra(1); 
    dfs1(1, -1), dfs2(1, 1);
    sgt.build();
    for (int j = 2; j <= tot; j++) {
        int u = edge[j].from, v = edge[j].to, w = edge[j].dis;
        if (ontree[j]) continue;
        int f = lca(u, v), x = sgt.query(dfn[f]);
        change(u, v, dis[u] + dis[v] + w);
        sgt.change(dfn[f], x);
    } 
    for (int i = 2; i <= n; i++) {
        int x = sgt.query(dfn[i]) - dis[i];
        cout << (x > 1e9 ? -1 : x) << '\n';
    }
}

::::

CF1163F Indecisive Taxi Fee

每次修改一条边权，求最短路。询问独立。

我们分类讨论一下，先求出最短路的边集 E_0，设原边权为 w_0，新边权为 w：

下面我们重点要解决的是 e \in E_0 且 w>w_0 的情况，仍然可以走原最短路 s-w_0+w，我们只要知道删去这条边的最短路即可。

设原最短路的路径是 P=\{e_1,e_2,e_3,\cdots,e_k\}。对于不在 P 中的顶点 u，放到最短路图上考虑可以发现 1 到 u 的最短路必定使用 P 的一段前缀，不会出现两段使用的情况。设前缀为 [1,L_u]。

同理可得，u 到 n 的最短路必定使用 P 的一段后缀，设前缀为 [R_u,n]。L_u,R_u 可以通过先 Dijkstra 求出 P 再正反跑最短路得到。

现在我们解决删边最短路问题。用一棵线段树来维护图 [l,r] 上不经过 [l,r] 段的最短路长度。对于不在最短路上的边 (u,v,w)，因为新的最短路可以改成过这条边，我们对于 [L_u+1,R_v] 作区间最值操作更新 dis_{1,u}+w+dis_{v,n}，同理对 [L_v+1,R_u] 也更新。由于我们是区间更新单点查询，写个标记永久化即可。

最终，我们在预处理 O((m+n) \log n)，单次查询 O(\log n) 的复杂度内解决了这道黑题。

:::info[代码]

const int N = 2e5 + 5;
const long long inf = 0x3f3f3f3f3f3f3f3f;

int n, m, q, e, w, u[N], v[N], w0[N];
int tot = 1, head[N];
struct Edge {
    int next, from, to; long long dis;
} edge[N << 1];
inline void add_edge(int u, int v, long long w) {
    edge[++tot].next = head[u], edge[tot].from = u, edge[tot].to = v, edge[tot].dis = w, head[u] = tot;
}

int tmp[N], pre[N], L[N], R[N], eid[N];
bool onpath[N];
namespace D {
    struct node {
        int to; long long dis;
        node(int x = 0, long long y = 0) : to(x), dis(y) {}
        bool operator< (const node& other) const {return dis > other.dis;}
    };

    void dijkstra(int s, long long *dis, int *from) {
        priority_queue<node> q;
        memset(dis, 0x3f, sizeof(long long) * (n + 1));
        dis[s] = 0, q.emplace(s, 0);
        while (!q.empty()) {
            int u = q.top().to; long long d = q.top().dis; q.pop();
            if (d != dis[u]) continue;
            for (int j = head[u]; j != 0; j = edge[j].next) {
                int v = edge[j].to; long long w = edge[j].dis;
                if (dis[v] > dis[u] + w) {
                    pre[v] = j / 2, dis[v] = dis[u] + w;
                    if (!onpath[v]) from[v] = from[u];
                    q.emplace(v, dis[v]);
                }
            }
        }
    }
}

int cnt;
struct segtree {
#define ls (rt << 1)
#define rs (rt << 1 | 1)
    long long mn[N << 2];
    void build(int l = 1, int r = cnt, int rt = 1) {
        mn[rt] = inf;
        if (l == r) return;
        int mid = (l + r) >> 1;
        build(l, mid, ls), build(mid + 1, r, rs);
    }
    void change(int tl, int tr, long long c, int l = 1, int r = cnt, int rt = 1) {
        if (tl > tr) return;
        if (tl <= l && r <= tr) return mn[rt] = min(mn[rt], c), void();
        int mid = (l + r) >> 1;
        if (tl <= mid) change(tl, tr, c, l, mid, ls);
        if (tr > mid) change(tl, tr, c, mid + 1, r, rs);
    }
    long long query(int x, int l = 1, int r = cnt, int rt = 1) {
        if (l == r) return mn[rt];
        int mid = (l + r) >> 1;
        if (x <= mid) return min(mn[rt], query(x, l, mid, ls));
        return min(mn[rt], query(x, mid + 1, r, rs));
    }
} sgt;

long long dis[2][N];

void _main() {
    cin >> n >> m >> q;
    for (int i = 1; i <= m; i++) {
        cin >> u[i] >> v[i] >> w0[i];
        add_edge(u[i], v[i], w0[i]), add_edge(v[i], u[i], w0[i]);
    }
    D::dijkstra(n, dis[1], tmp);
    L[1] = R[1] = 0, onpath[1] = true;
//  for (int i = 1; i <= n; i++) cerr << pre[i] << ' ';
    int cur = 1;
    for (int i = 1; cur != n; i++, cnt++) {
        int e = pre[cur];
        eid[e] = i;
        cur = (u[e] == cur) ? v[e] : u[e];
        L[cur] = R[cur] = i, onpath[cur] = true;
    }
    D::dijkstra(1, dis[0], L), D::dijkstra(n, dis[1], R);
    sgt.build();
    for (int j = 1; j <= m; j++) {
        if (eid[j]) continue;
        sgt.change(L[u[j]] + 1, R[v[j]], dis[0][u[j]] + w0[j] + dis[1][v[j]]);
        sgt.change(L[v[j]] + 1, R[u[j]], dis[0][v[j]] + w0[j] + dis[1][u[j]]);
    }
    while (q--) {
        cin >> e >> w;
        if (eid[e]) {
            if (w <= w0[e]) cout << dis[0][n] - w0[e] + w;
            else cout << min(dis[0][n] - w0[e] + w, sgt.query(eid[e]));
        } else {
            if (w >= w0[e]) cout << dis[0][n];
            else cout << min({
                dis[0][n], 
                dis[0][u[e]] + w + dis[1][v[e]], 
                dis[0][v[e]] + w + dis[1][u[e]]
            });
        }
        cout << '\n';
    }
}

:::

P2483 【模板】k 短路 / [SDOI2010] 魔法猪学院

首先我们发现这题要求的就是一个最大的 k 使得前 k 短路之和在 E 以内。

关于 A*，它死了。我们用最短路算法来解决这个题。在反图上以 t 为源点跑最短路并建立任意一棵最短路树，那么从 s 到 t 的路径由树边和非树边构成，我们用一个非树边集合来表示一条路径。

在学堆的时候，我们经常用它解决前 k 小问题，就是不断扩展当前状态，k 短路也是同理的。我们用一个堆来维护当前的非树边集合，取出最小的集合进行扩展，而其转移有两种：

  1. 在序列中插入一条边。我们对于每个点 u 维护一个 u 到 t 树边路径上的非树边集合，则选择这条边的代价为 dis_v-dis_u+w。这一步也可以用堆实现，但是如果直接开 n 个堆复杂度就炸了。可以发现，一个堆是由其他一些堆合并出来的，我们用可持久化可并堆维护即可。
  2. 用一条边替换最后一条边。我们找到这个方案的历史版本，把根删掉即可，也就是合并根的左右儿子作为新根。

这还是堆问题的常见套路，通过构造状态分析转移，控制状态数和唯一性。可以证明，每次只会扩展出三个节点，状态数是 O(n+k) 的。使用可持久化左偏树，总复杂度 O((n+m) \log n +k\log k)。

:::info[代码]

const int N = 2e5 + 5;

int n, m, u, v, p[N]; 
double e, w;
int tot = 0, head[N];
struct Edge {
    int next, to; double dis;
} edge[N << 1];
inline void add_edge(int u, int v, double w) {
    edge[++tot].next = head[u], edge[tot].to = v, edge[tot].dis = w, head[u] = tot;
}

namespace T {
    int cnt = 0;
    struct node {
        int l, r, dis, fa;
        double val;
    } tr[N << 5];
    int create(int fa, double val) {
        return tr[++cnt] = {0, 0, 0, fa, val}, cnt;
    }
    int copy(int x) {
        return tr[++cnt] = {tr[x].l, tr[x].r, tr[x].dis, tr[x].fa, tr[x].val}, cnt;
    }
    int merge(int a, int b) {
        if (!a || !b) return a ? a : b;
        if (tr[a].val > tr[b].val) swap(a, b);
        int nw = copy(a);  // 可持久化
        tr[nw].r = merge(tr[nw].r, b);
        if (tr[tr[nw].l].dis <= tr[tr[nw].r].dis) swap(tr[nw].l, tr[nw].r);
        tr[nw].dis = tr[nw].r ? tr[tr[nw].r].dis + 1 : 0;
        return nw;
    }
    int rt[N];
}

namespace D {
    int tot = 0, head[N];
    struct Edge {
        int next, to; double dis;
    } edge[N << 1];
    inline void add_edge(int u, int v, double w) {
        edge[++tot].next = head[u], edge[tot].to = v, edge[tot].dis = w, head[u] = tot;
    }

    struct node {
        int to; double dis;
        node(int x = 0, double y = 0.0) : to(x), dis(y) {}
        bool operator< (const node& other) const {return dis > other.dis;}
    };

    int fa[N];
    double dis[N];
    priority_queue<node> q;
    void dijkstra(int s) {
        fill(dis + 1, dis + n + 1, 1e9);
        dis[s] = 0, q.emplace(s, 0.0);
        while (!q.empty()) {
            int u = q.top().to; double d = q.top().dis; q.pop();
            if (d != dis[u]) continue;
            for (int j = head[u]; j != 0; j = edge[j].next) {
                int v = edge[j].to; double w = edge[j].dis;
                if (dis[v] > dis[u] + w) {
                    dis[v] = dis[u] + w, fa[v] = j;
                    q.emplace(v, dis[v]);
                }
            }
        }
    }
}

void _main() {
    cin >> n >> m >> e;
    for (int i = 1; i <= m; i++) {
        cin >> u >> v >> w;
        if (u != n) add_edge(u, v, w), D::add_edge(v, u, w);
    }
    D::dijkstra(n);
    iota(p + 1, p + n + 1, 1);
    sort(p + 1, p + n + 1, [&](int a, int b) -> bool {
        return D::dis[a] < D::dis[b];
    });
    for (int i = 1; i <= n; i++) {
        int u = p[i];
        for (int j = head[u]; j != 0; j = edge[j].next) {
            if (j == D::fa[u]) continue;
            int v = edge[j].to; double w = edge[j].dis;
            T::rt[u] = T::merge(T::rt[u], T::create(v, D::dis[v] + w - D::dis[u]));
        }
        int from = edge[D::fa[u]].to;
        T::rt[u] = T::merge(T::rt[u], T::rt[from]);
    }
    e -= D::dis[1];
    int res = 1;
    priority_queue<D::node> q;
    q.emplace(T::rt[1], T::tr[T::rt[1]].val);
    while (!q.empty()) {
        int u = q.top().to; double d = q.top().dis; q.pop();
        if (e < d + D::dis[1]) return cout << res, void();
        e -= d + D::dis[1], res++;
        int ls = T::tr[u].l, rs = T::tr[u].r, fa = T::tr[u].fa;
        if (ls) q.emplace(ls, d - T::tr[u].val + T::tr[ls].val);
        if (rs) q.emplace(rs, d - T::tr[u].val + T::tr[rs].val);
        if (T::rt[fa]) q.emplace(T::rt[fa], d + T::tr[T::rt[fa]].val);
    }
    cout << res;
}

:::