基于NetworkX求解单源最短路径下最大权值非必要边移除问题

核心逻辑 #

你的需求本质是在保证所有节点到首都A的最短距离不变的前提下，让保留的公路总长度最小，对应被移除的公路总长度最大，完全不需要穷举所有路径组合，可按以下步骤实现：

• 第一步调用nx.single_source_dijkstra计算首都A到所有节点的最短距离数组d，时间复杂度仅为O(M + NlogN)，N是节点数、M是边数
• 第二步筛选所有符合最短路径规则的候选边：对任意边(u, v)，权值为w，如果满足d[u] + w == d[v]，说明这条边可以作为v到A的最短路径的一段
• 第三步对每个非A的节点v，从所有指向它的候选边里选择权值最小的一条加入保留图即可。如果有多个相同最小权的边任选其一即可，不影响总权结果。

高效实现代码 #

import networkx as nx
from matplotlib import pyplot as plt

# 初始化原图
g = nx.Graph()
g.add_edge("A", "B", weight=2)
g.add_edge("B", "C", weight=2)
g.add_edge("C", "D", weight=3)
g.add_edge("D", "A", weight=1)

base = "A"
# 第一步：算单源最短距离
d, _ = nx.single_source_dijkstra(g, source=base, weight="weight")

# 第二步：构建保留图
solution_graph = nx.Graph()
for v in g.nodes:
    if v == base:
        continue
    min_edge = None
    min_weight = float("inf")
    # 遍历v的所有邻居，找符合条件的最小权候选边
    for u in g.neighbors(v):
        w = g.edges[u, v]["weight"]
        if d[u] + w == d[v]:
            if w < min_weight:
                min_weight = w
                min_edge = (u, v, w)
    # 加入最小边
    if min_edge:
        solution_graph.add_edge(min_edge[0], min_edge[1], weight=min_edge[2])

# 计算保留边总权，验证结果
total_keep = sum(e[2]["weight"] for e in solution_graph.edges(data=True))
print(f"保留边总权：{total_keep}，对应移除边总权：{sum(e[2]['weight'] for e in g.edges(data=True)) - total_keep}")

# 绘制结果
labels = {n: n for n in solution_graph.nodes}
edge_labels = {(e[0], e[1]): e[2]["weight"] for e in solution_graph.edges(data=True)}
pos = nx.spring_layout(solution_graph)
nx.draw(solution_graph, pos=pos, with_labels=True, labels=labels)
nx.draw_networkx_edge_labels(solution_graph, pos=pos, edge_labels=edge_labels)
plt.savefig("solution.png")

运行后输出和你之前穷举得到的最优结果一致：保留边总权：5，完全符合需求。

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