图

最短路

• 边权均为 的无向图上，最短路上的节点的 deg 总和是 量级的

证明

考虑最短路上的不相邻的任意两个节点，这两个节点之间不可能有边。

考虑最短路外的任意一个节点，如果它与四个最短路上的阶段均有连边，也会存在矛盾

如图，红色路径一定比黑色路径短

所以设 是最短路上的节点数量。我们有最短路上的所有节点的度数和不大于 ，是 量级的。