带负权边的无向图上的最短路径问题

有趣的问题
  1. 路与路径
  2. 带负权边的无向图上的最短路径问题
    1. 条件
    2. 算法
    3. 解释 / 证明
    4. 例
  3. 附

路与路径

从前我一直有这样一个问题：最短路取负不就变成最长路了吗？为什么最短路有这么多算法，而最长路就 NP-Hard 了呢？

这是因为这里没有严格区分 trail（路或迹，可包含重复节点）和 path（路径，有时称简单路径，不包含重复节点）。

我们平常所说的最短路问题是希望计算 path，但算法其实求的是 trail，因为当有负环时会认为是 \(-\infty\)，而在有负环的图上求 shortest path 这件事情是 NP-Hard 的。

所以最短路和最长路确实是等价的，多项式时间内可解和不可解的根本区别是否可包括重复点。当然对于正权图，最短路和最短路径是等价的，因为 trail 中如果有正环那么删掉更优。

带负权边的无向图上的最短路径问题

上述关于最短路的讨论是关于有向图的。那么对于一个有负边权的无向图，其最短路（trail）当然是 \(-\infty\)，现在我们希望求其最短路径（path）。如对于下图，\(A\) 和 \(B\) 之间的 shortest trail 为 \(-\infty\)，而 shortes path 为 \(-1\)。

即下面给出一种求解带负权边的无向图上的单源汇最短路径问题的算法。此为带负权环的最短路径问题的特例，只能包含长度为 \(2\) 的负权环。（因为无向边可以用两条有向边表示。）

条件

带权无向连通图 \(G\)，不含（无向图意义下的）负权环，源点 \(s\)，汇点 \(t\)，且 \(s\neq t\)。

算法

  1. 建图 \(G'\)，除 \(s, t\) 外的每个点 \(u\) 拆成两个 \(u'\) 和 \(u''\)并相连，权值为 \(0\)。每条边 \(w\) 拆成 \(w'\) 和 \(w''\)，对于 \(w(u, v) = d\)，\(w'\) 和 \(w''\) 分别与 \(u, v\) 拆出的点相连，并将边数较少一侧的边权设为 \(d\)。称变换后的边集为 \(g(uv)\)。如下图所示。
  2. 在 \(G'\) 上跑一般图最小权最大匹配（带花树算法）。\(G'\) 定有完美匹配 [1]，记为 \(M\)。
  3. \(g(uv)\) 中只会有 \(1\) 或 \(2\) 条边属于 \(M\) [2]。令 \(S\) 表示有 \(2\) 条边属于 \(M\) 的边集。又，\(V(G)-\{s,t\}\) 有 \(0\) 或 \(2\) 条邻接边在 \(S\) 中，而 \(s\) 和 \(t\) 有 \(1\) 条邻接边在 \(S\) 中 [3]。因此 \(S\) 包含一条 \(s\) 到 \(t\) 的路径 \(P\)，还有可能有一些孤立的环。而每个环上的权值和为 \(0\) [4]。故 \(d'(M) = d(S) = d(P)\)。由于 \(M\) 是最小权匹配，故 \(P\) 是最短 \(s-t\) 路径 [5]。

时间复杂度为带花树的复杂度 \(O(V(G')^3)\)。由于这是个稀疏图，复杂度可以优化到 \(O(V(G')E(G') \lg V(G'))\)。其中 \(V(G') = 2 V(G) + 2 E(G)\)，\(E(G') = V(G) + 5 E(G)\)。

解释 / 证明

  1. 由于 \(G\) 是连通图，故存在 \(s, t\) 之间的一条路径。对于这叫路径上的边，将 \(g(uv)\) 中两边的边作为匹配；对于其余边和点，匹配 \(u' - u'', w' - w''\)。这样可以构造出一个完美匹配。如下图所示。
  2. 如果 \(w'\) 与 \(w''\) 之间的边属于 \(M\)，则两边的边定不属于 \(M\)；否则两边各有一条边属于 \(M\)。故 \(g(uv)\) 有 \(1\) 或 \(2\) 条边属于 \(M\)。
  3. 对于 \(u\in G-\{s,t\}\)，如果 \(u'\) 和 \(u''\) 之间的边在 \(M\) 中，则 \(u\) 没有邻接边属于 \(S\)；否则，\(u'\) 和 \(u''\) 分别与边所表示的顶点 \(w_1\) 和 \(w_2\) 匹配，即 \(u\) 有两条邻接边 \(w_1\) 和 \(w_2\) 在 \(S\) 中。
  4. 如果存在正权环，则改为匹配 \(u'\) 与 \(u''\) 之间的边以及 \(w'\) 与 \(w''\) 之间的边，得到新匹配中这部分的权值为 \(0\)，更优，矛盾。且我们的假设中此图不含负权环。故若有环则其权值定为 \(0\)。
  5. 图 \(G\) 中的边权 \(d\) 被计算入 \(M\) 中当且仅当这条边在 \(S\) 中。又，环上权值和为 \(0\)，故最小匹配等于最短路长度。且完美匹配和最短路可以相互构造，即等价。

例

附

problem solving 图论