图节点组间非零最短路径权重的最小值求解方法

看起来你已经搞定了全节点对的最短路径计算，现在就差从结果里筛选出需要的非零最小值了——这个需求很常见，我来给你一步步拆解怎么做。

首先，假设你已经有了存储所有节点对最短路径的字典，结构大概是这样的（以Python为例）：

# 示例结构：key是源节点，value是{目标节点: 路径权重}的字典
shortest_paths = {
    10: {10: 0, 45: 12, 76: 8, 23: 15},
    76: {10: 8, 45: 5, 76: 0, 23: 9},
    45: {10: 12, 45: 0, 76: 5, 23: 6},
    # 其他节点...
}

接下来分两种常见场景处理：

场景1：单个目标节点，查询多个源节点到它的非零最短路径 #

比如你要找节点10、76到节点45的非零最短路径最小值，代码可以这么写：

# 定义目标节点和要查询的源节点列表
target_node = 45
source_nodes = [10, 76]

# 存储结果的字典
min_results = {}

for source in source_nodes:
    # 获取源到目标的路径权重，排除0（节点到自身的情况）
    distance = shortest_paths[source].get(target_node)
    if distance and distance > 0:
        min_results[(source, target_node)] = distance
    else:
        min_results[(source, target_node)] = None  # 无有效路径的情况

# 输出结果
for (src, tgt), dist in min_results.items():
    print(f"节点{src}与节点{tgt}间的非零最短路径最小值：{dist}")

运行后会得到：

节点10与节点45间的非零最短路径最小值：12
节点76与节点45间的非零最短路径最小值：5

场景2：多个目标节点，查询源节点到该组内任意节点的非零最短路径最小值 #

如果你的输入节点组有多个节点（比如{45,23}），要找源节点到组内所有节点的非零最短路径里的最小值，代码调整如下：

# 定义目标节点组和源节点列表
target_group = {45, 23}
source_nodes = [10, 76]

min_results = {}

for source in source_nodes:
    # 收集源到目标组内所有非零的路径权重
    valid_distances = [
        dist for tgt, dist in shortest_paths[source].items()
        if tgt in target_group and dist > 0
    ]
    # 取最小值（如果有有效路径的话）
    min_results[source] = min(valid_distances) if valid_distances else None

# 输出结果
for src, dist in min_results.items():
    print(f"节点{src}到目标组{target_group}的非零最短路径最小值：{dist}")

这个例子里，节点10到{45,23}的非零最短路径是12（到45）和15（到23），最小值是12；节点76的是5（到45）和9（到23），最小值是5。

关键注意点 #

• 排除零值：因为节点到自身的路径权重通常是0，我们需要的是不同节点间的路径，所以一定要加上dist > 0的判断。
• 无路径处理：如果某个源节点和目标节点/组没有连通（或者只有自身），valid_distances会是空列表，这时候可以返回None或者根据你的业务需求设置默认值（比如无穷大）。
• 效率优化：如果你的图非常大，全节点对的最短路径字典会占用很多内存，其实可以只针对需要的源节点和目标节点单独计算路径，不用预先算所有节点对——但既然你已经有了全量字典，基于它来筛选肯定是最快的。

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