如何构造满足最短路径约束的加权图最小权重最优树？

问题概述 #

你需要构建一棵满足以下全部条件的最优树：

• 包含图中所有顶点（是一棵生成树）
• 所有边都来自原加权图
• 从指定顶点U出发到任意其他顶点的路径，都是原图中的最短路径
• 目标是让这棵树的总边权之和最小

这本质上是寻找以U为根的最小总权重最短路径树——注意，从U出发的最短路径树可能有多棵，我们要选其中边权总和最小的那一棵。

解法思路 #

当图中所有边权非负时（比如你的示例），可以基于Dijkstra算法来实现，步骤如下：

1. 计算最短路径距离：先用Dijkstra算法算出从起点U到图中每个顶点v的最短路径长度dist[v]
2. 选择最优边：对每个非起点的顶点v，找出所有满足dist[u] + weight(u, v) = dist[v]的边(u, v)（这些边都能作为v在最短路径树中的父边），然后从中挑选权重最小的那条边
3. 求和得到总权重：把所有选中的边的权重加起来，就是这棵最优树的总权重

如果图中有负权边，可以改用Bellman-Ford算法来计算最短路径，后续步骤保持一致。

示例详细推导 #

我们用你给出的示例来一步步计算：

输入解析

输入内容：6 8 1 2 30 1 3 20 2 3 50 4 2 100 2 5 40 3 5 10 3 6 50 5 6 60 4
拆解后：

• 顶点总数：6
• 边总数：8
• 8条无向边（起点 终点 权重）：
  • 1-2，权重30
  • 1-3，权重20
  • 2-3，权重50
  • 4-2，权重100
  • 2-5，权重40
  • 3-5，权重10
  • 3-6，权重50
  • 5-6，权重60
• 起点U：4

步骤1：计算从4到所有顶点的最短路径距离

• dist[4] = 0（起点到自身的距离）
• dist[2] = 100（直接走4-2）
• dist[1] = dist[2] + 30 = 130（路径4->2->1）
• dist[5] = dist[2] + 40 = 140（路径4->2->5）
• dist[3] = min(dist[2]+50, dist[1]+20, dist[5]+10) = min(150, 150, 150) = 150（三条路径都能到达，长度相同）
• dist[6] = min(dist[3]+50, dist[5]+60) = min(200, 200) = 200（两条路径长度相同）

步骤2：为每个顶点选择最小权重的符合条件的边

• 顶点2：只有边4-2满足dist[4]+100=dist[2]，选中这条边，权重100
• 顶点1：只有边2-1满足dist[2]+30=dist[1]，选中这条边，权重30
• 顶点5：只有边2-5满足dist[2]+40=dist[5]，选中这条边，权重40
• 顶点3：满足条件的边有2-3（权重50）、1-3（权重20）、5-3（权重10），选最小的5-3，权重10
• 顶点6：满足条件的边有3-6（权重50）、5-6（权重60），选最小的3-6，权重50

步骤3：计算总权重

把选中的边权重相加：100 + 30 + 40 + 10 + 50 = 230，和示例输出一致。

注意事项 #

• 一定要确保筛选所有能构成最短路径的边，不能遗漏（比如示例中顶点3的5-3边很容易被忽略）
• 如果有负权边，Dijkstra算法不再适用，必须改用Bellman-Ford或者SPFA算法来计算最短路径

内容的提问来源于stack exchange，提问作者Mohammad Abdollahzadeh