带权图与无权图详解

Mohammed Islam Hadjoudj

Expert Operations Research Engineer

1. 权重是函数，不是图的一部分

图是一对集合 G = (V, E)，这个定义中根本没有提到数字。距离、成本、容量和时长都来自外部，是附加在同一边集上的一个独立函数：

G = (V, E)                    图：哪些顶点对相连
w: E → ℝ                    权重函数：每条连接的代价

标准教材有意强调这种分离。Bondy 和 Murty 把带权图定义为一个图加上为每条边指定的一个实数，然后把子图的权重定义为其各边权重之和，而这正是最短路径或最小生成树所要最小化的量。Diestel 也以同样的方式处理权重，把它们视为叠加在一个不变的组合对象之上的额外数据。

把 w 放在图之外并非吹毛求疵，它带来三点好处：

• 同一个图可以承载多种成本模型。一个道路网络就是一个图 G ，上面有三个函数：公里数、分钟数、燃油升数。换一个函数就会改变每个答案，而无需触碰任何顶点或边。
• 条件附加在函数上，而不是结构上。 “Dijkstra 需要非负权重”是关于 w的陈述。图本身对此毫不在意。
• 结构性结论保持不变。连通性、平面性、二部性、度序列以及握手引理都只是 (V, E) 的性质，因此添加权重不会改变其中任何一个。

于是，无权图就是没有提供此类函数的图，下一节会说明，这等同于提供了最乏味的那个函数。

2. 无权意味着每个权重都是 1

要同时理解这两种情况，最清晰的方式是不再把“无权”看作没有权重，而是把它看作一种特定的权重选择：

无权图就是满足以下条件的带权图： w(e) = 1 对每条边成立。于是路径的权重就是它的边数，所以“最短路径”意味着“边数最少”。

一切都源于这一次替换。广度优先搜索找到边数最少的路径，它恰好就是 Dijkstra 算法在所有权重都为 1 时退化成的样子：优先队列从不需要重新排序，因为距离本来就按非递减的整数顺序出队，一个普通的 FIFO 队列就能在 O(n + m)内完成同样的工作。Edward Moore 1959 年的论文“The shortest path through a maze”提出并解决的正是这个单位权重问题，这个算法通常也追溯到这篇论文。

这种替换反过来也成立，而权重的代价正体现在这里。给同一个图赋予任意正权重，FIFO 队列就不再适用，因为边更多的路径现在可能更便宜。你需要优先队列，运行时间从 O(n + m) 变为使用二叉堆时的 O(m log n) ，或使用 Fredman 和 Tarjan（1987）的斐波那契堆时的 O(m + n log n) 。

3. 最短路径并非最短路径

这张图展示了全部区别。同样的五个顶点、同样的五条边、同样的问题，根据有没有数字，会得到两个不同的答案。

完整写出来，这个图是

V = {A, B, C, D, E}
E = { {A,B}, {B,C}, {C,D}, {A,D}, {D,E} }
w =    1       1       1       7       2

两个问题的答案如下：

注意，带权的答案在两行中都使用了更多的边。这是常态，而不是刻意构造的情况：绕行高速公路经过的路口更多，花费的分钟却更少。在带权图上运行 BFS 得到的不是近似答案，而是另一个问题的答案，两者之间的差距没有上界。把 {A, D} 的权重提高到一百万，BFS 仍然会返回它。

4. 权重的含义：三种组合方式

“带权图”只是一个容器，而不是一种含义。在选择算法之前，你必须先回答一个问题：路径上的权重如何组合成你关心的那个值？常见的答案有三种，它们导向三个不同的问题。

乘性技巧值得详细说明，因为从路由到自然语言解码，它无处不在。沿路径最大化概率之积，等同于最小化它们负对数之和，因为 -log 是单调递减的，并把乘积变成求和。由于每个概率至多为 1，每个 -log w 都是非负的，所以 Dijkstra 可以直接使用，不需要任何特殊算法。

还有一个区别造成的建模错误比以上所有问题都多，而且它与算术毫无关系：

数值越大，是表示越近还是越远？在距离图中，权重大是坏事，你要最小化。在相似度图中，权重大是好事，你要最大化。两者正好相反，而文件格式不会告诉你手里的是哪一种。

相关性网络、共同购买图和嵌入相似度图都是按相似度加权的，因此把它们交给最短路径程序，算出的是经过最不相似链接的路径。如果你需要从相似度得到距离，就要有意识地转换： d = 1 - s 适用于取值在 [0, 1] 内的相似度，或者 d = 1/s，或者 d = -log s。每种选择都会改变路径的排序，所以这是一个建模决策，而不是走形式。

5. 权重替你选择算法

一旦组合规则是加性的，仅凭权重函数的形态就能决定算法。这正是带权与无权之区别的实际核心。

表中有两项值得说明。 0-1 BFS 基于一个巧妙的观察：如果权重只有 0 或 1，就根本不需要堆，双端队列可以免费保持边界有序，从而恢复线性时间。 Johnson 算法出自他 1977 年发表在 Journal of the ACM上的论文，是在带负权边的图上保持 Dijkstra 速度的标准方法：它加入一个势函数，使每条重新赋权的边都非负，同时保持哪些路径最短不变。

在无权情形的边界上还有一个引人注目的结果。Thorup 在 1999 年证明，对于带正整数权重的无向图，单源最短路径可以在线性时间内求出，与 BFS 相当，其方法是利用整数权重的结构，而不是比较距离。对于比较-加法模型中的任意实数权重，目前还没有类似的线性时间结果，这提醒我们，“带权”不是一个问题，而是一族问题，其难度取决于权重的形态。

6. 负权重，以及 Dijkstra 为何失效

Dijkstra 1959 年的短文假设权重非负，而这个假设是承重的，并非装饰。算法是贪心的：一旦把某个顶点从队列中取出，就宣布它已确定，并且再也不回头检查。只有当之后发现的路径不可能更便宜时，这才是正确的，而非负性恰好保证了这一点，因为延长路径只会增加成本。

只要引入一条负权边，这个保证就会失效。下面是一个小到可以手工追踪的反例，而且没有并列情况，出队顺序是确定的：

追踪一下：队列取出距离为 0 的 S，把 A 松弛为 1，C 松弛为 3。取出距离为 1 的 A，把 B 松弛为 2。取出距离为 2 的 B，并标记为已确定。直到这时，它才取出距离为 3 的 C，发现权重为 -5 的弧 C → B ，它本会使 B 的距离变为 -2。由于 B 已经确定，这一改进被丢弃，算法报告 2 而不是 -2。

有两点澄清比反例本身更重要：

• 负权重不等于负环。一个图可以有负权边，却仍有定义良好的最短路径，这正是 Bellman-Ford 以 O(nm)处理的情形。真正彻底破坏问题的是总权重为负的环，因为你可以反复绕行，把成本压到负无穷。Bellman-Ford 能检测出这种情况，而不是悄悄返回荒谬的结果。
• 在无向图中，一条负权边本身就是负环。沿它走过去再走回来，你付出的代价是 2w < 0。所以负权重实际上是有向图的话题；在无向图上，最短途径问题无界，最短简单路径问题则是 NP 困难的。关于有向图与无向图的配套指南讨论了这一边界。

负权重并不罕见。套利链把货币兑换定价为乘积，乘积再变成负对数之和，而有利可图的环在模型中就表现为负环。这是负权检测的标准教科书应用，也正因如此，Bellman-Ford 多出的那个 n倍因子是值得的。

7. 只有带权时才存在的问题

有些问题在无权时并不是更难，而是空洞。最明显的例子是最小生成树。

在无权连通图中，每棵生成树恰有 n - 1 条边，所以每棵生成树都是最小的，任何一次遍历都能解决问题：BFS 或 DFS 树本身就是答案。加上权重，这个问题才变得真实，因为生成树的总成本各不相同，而找出最便宜的那棵，正是 Borůvka 在 1926 年、Kruskal 在 1956 年和 Prim 在 1957 年各自解决的问题。

在贯穿示例中，最小生成树选取 {A,B}、 {B,C}、 {C,D} 和 {D,E} ，总权重为 5，并舍弃了昂贵的 {A,D} （权重 7）。如果不带权，这个图的四棵生成树都一样好。

最大流是生成树情形的镜像。容量就是权重函数，所以无权流网络意味着单位容量，而在这种特殊情形下，根据 Menger 定理，最大流归结为统计边不相交路径的数目。Ahuja、Magnanti 和 Orlin 的 Network Flows 是一般带权处理的标准参考书，其中每条弧通常同时带有容量和成本，也就是一个图上有两个权重函数。

8. 存储权重，以及零与无穷大的陷阱

两种标准表示都可以用显而易见的方式扩展，而且各有一种值得点明的失效模式。

邻接矩阵。元素 (u, v) 不再是 0 和 1，而是存放这条边的权重。陷阱立刻出现：没有边的格子里放什么？0 是诱人的默认值，但它是错的，因为 0 是完全合法的权重，两种情况会变得无法区分。在最短路径场景下，用 ∞ 表示“没有边”，因为它是最小化运算的单位元，并在对角线上保留 0。在无权矩阵中，同一个格子用值 0 表示“没有边”，这正是从无权代码移植到带权代码时在这里出错的原因。

无权       A[u][v] = 连通则为 1，否则为 0
带权       A[u][v] = 连通则为 w(u,v)，否则为 ∞      （对角线为 0）

哨兵 bug   用 A[u][v] = 0 表示“没有边”会让权重为 0 的边
           不可见，所有距离都塌缩为 0

邻接表。每个条目从单个顶点变为一个对，因此表中存放的是 (邻居, 权重)。其他一切不变，这就是邻接表成为带权问题默认选择的原因：每条存储的边只多占一个数字的内存，遍历循环完全相同。

还有第三种格式对带权图特别重要。边列表由三元组 (u, v, w) 构成，它是 Kruskal 算法的天然输入，该算法按权重对整个列表排序；它也是 Bellman-Ford 的天然输入，后者依次松弛每条边。两者都不需要查找邻居，所以都完全不需要邻接结构。

9. 度变成强度

权重不仅改变算法，也改变描述性统计量。顶点的度在带权情形下的对应物是它的强度，即其关联边的权重之和：

deg(v)  =  关联边的数量                     无权计数
s(v)    =  ∑ w(e)，对 v 的所有关联边求和     带权总和

Barrat、Barthélemy、Pastor-Satorras 和 Vespignani 在 2004 年关于带权网络的 PNAS 论文中引入了这个术语，它之所以重要，是因为这两个量对顶点的排序可能完全不同。一个拥有许多小型支线航线的机场，度高而强度低；一个拥有四条巨大远程航线的枢纽，度低而强度高。问“哪个机场最重要”，取决于你计算的是哪个量，答案会不同，而且两者都没有错。

同样的分歧贯穿网络分析的其他部分。Newman 2004 年的论文“Analysis of weighted networks”展示了聚类系数、模块度和中心性如何各自获得带权版本，以及同一指标的带权与无权版本在同一数据上经常不一致。当你报告一个网络统计量时，说明它是否使用了权重不是脚注，而是定义的一部分。

10. 何时添加权重，何时不要

权重不是免费的。它们让你失去线性时间算法，在每一步都增加一个建模决策，并引入无权图根本不存在的尺度敏感性。只有当答案真正取决于数值大小时，才使用它们：

• 添加权重，当边之间存在可测量的差异并且会改变决策时：道路长度、链路容量、交易金额、相关强度、相似度分数。
• 保持无权，当关系本质上是二元的（国家是否相邻、是否存在依赖），当你手头的数字是连你自己都不愿辩护的噪声代理，或者当问题纯粹是结构性的，例如连通性或二部性。
• 改用阈值，当权重存在但不可靠时。保留高于某个阈值的边、舍弃其余的边，可以把有噪声的带权图变成站得住脚的无权图。要说明阈值，因为结果通常依赖于它。

带权数据有两点特别的注意事项。第一，尺度很重要：把所有权重乘以一个正常数，最短路径和最小生成树都不会改变，因为两者都是最小化一个和，但任何把权重与绝对阈值比较的统计量都会改变，而乘以负数则会把问题完全颠倒。第二，单位必须一致，才能把权重相加。在一个权重函数中混用分钟和公里，得到的数字没有任何算法能够解释，而代码也不会报错。

11. 常见错误

• 在带权图上运行 BFS。这是所有错误中最常见的。它返回边数最少的路径，这是另一个问题的正确答案，而误差没有上界，正如第 3 节所示。
• 用 0 作为“没有边”的哨兵值。在出现真正权重为 0 的边之前一切正常，之后就会悄无声息地出错。对最小化问题请使用无穷大。
• 把相似度图交给最短路径程序。它会忠实地找出经过最弱链接的路线。先把相似度转换为距离，并说明转换方式。
• 在有负权重时使用 Dijkstra。它不仅会在某些输入上失去最优性保证，还会返回具体的错误数字，正如第 6 节所示。请使用 Bellman-Ford，全源问题则用 Johnson 算法。
• 以为负权边就意味着问题无解。只有负环才会使最短路径无定义。Bellman-Ford 能处理其余情况，如果存在负环也会报告出来。
• 把不同单位的权重相加。分钟加公里毫无意义，而且没有任何算法会提醒你。
• 报告带权网络统计量却不加说明。度与强度，以及由它们派生的中心性，经常对同样的顶点给出不同的排序。
• 忘记结构没有改变。连通性、二部性和度序列都不依赖于 w。如果带权算法给出的答案与其中某一项矛盾，那么错误出在赋权上，而不在理论上。

12. 术语表

14. 参考文献

以上定义、算法和归属均出自以下文献，按时间顺序排列。

1. Borůvka, O. (1926). "O jistém problému minimálním"（关于某个极小问题）。 Práce Moravské Přírodovědecké Společnosti 3，37 至 58 页。最早的最小生成树算法。
2. Kruskal, J. B. (1956). "On the Shortest Spanning Subtree of a Graph and the Traveling Salesman Problem." Proceedings of the American Mathematical Society 7(1)，48 至 50 页。
3. Prim, R. C. (1957). "Shortest Connection Networks and Some Generalizations." Bell System Technical Journal 36(6)，1389 至 1401 页。
4. Bellman, R. (1958). "On a Routing Problem." Quarterly of Applied Mathematics 16(1)，87 至 90 页。能容许负权重的最短路径。
5. Dijkstra, E. W. (1959). "A Note on Two Problems in Connexion with Graphs." Numerische Mathematik 1，269 至 271 页。文中明确提出了非负性假设。
6. Moore, E. F. (1959). "The Shortest Path Through a Maze." Proceedings of an International Symposium on the Theory of Switching，第二部分，285 至 292 页。Harvard University Press。单位权重情形，即如今所说的 BFS。
7. Johnson, D. B. (1977). "Efficient Algorithms for Shortest Paths in Sparse Networks." Journal of the ACM 24(1)，1 至 13 页。通过重新赋权消除负权边。
8. Fredman, M. L. and Tarjan, R. E. (1987). "Fibonacci Heaps and Their Uses in Improved Network Optimization Algorithms." Journal of the ACM 34(3)，596 至 615 页。O(m + n log n) 的 Dijkstra。
9. Ahuja, R. K., Magnanti, T. L. and Orlin, J. B. (1993). Network Flows: Theory, Algorithms, and Applications. Englewood Cliffs：Prentice Hall。关于以容量和成本为权重的标准参考书。
10. Thorup, M. (1999). "Undirected Single-Source Shortest Paths with Positive Integer Weights in Linear Time." Journal of the ACM 46(3)，362 至 394 页。
11. West, D. B. (2001). Introduction to Graph Theory，第 2 版。Upper Saddle River：Prentice Hall。
12. Barrat, A., Barthélemy, M., Pastor-Satorras, R. and Vespignani, A. (2004). "The Architecture of Complex Weighted Networks." Proceedings of the National Academy of Sciences 101(11)，3747 至 3752 页。顶点强度的出处。
13. Newman, M. E. J. (2004). "Analysis of Weighted Networks." Physical Review E 70，056131。标准网络指标的带权版本。
14. Bondy, J. A. and Murty, U. S. R. (2008). Graph Theory. Graduate Texts in Mathematics 244。伦敦：Springer。第 1 节中带权图定义的出处。
15. Cormen, T. H., Leiserson, C. E., Rivest, R. L. and Stein, C. (2009). Introduction to Algorithms，第 3 版。马萨诸塞州剑桥：MIT Press。
16. Diestel, R. (2017). Graph Theory，第 5 版。Graduate Texts in Mathematics 173。柏林：Springer。