NetworkX中single_source_dijkstra_path_length对不可达节点的返回值是多少

核心结论 #

调用single_source_dijkstra_path_length方法计算有向图最短路径长度时，从源节点出发不可达的节点，不会出现在方法返回的字典结果中，该字典仅包含所有可达节点和对应的最短路径长度，其中源节点自身的路径长度固定为0。

示例验证 #

你可以用如下代码验证该行为：

import networkx as nx

# 构造测试有向图：存在边1→2→3，节点4无任何连接
G = nx.DiGraph()
G.add_weighted_edges_from([(1, 2, 1), (2, 3, 1)])
G.add_node(4)

# 以节点1为源节点计算最短路径长度
path_length = nx.single_source_dijkstra_path_length(G, source=1)
print(path_length)
# 输出结果：{1: 0, 2: 1, 3: 2}，不可达的节点4不在返回字典内

扩展处理（可选） #

如果你需要包含所有节点的结果，给不可达节点设置无穷大作为默认值，可以自行补全结果：

import math
full_path_length = {node: path_length.get(node, math.inf) for node in G.nodes}
print(full_path_length)
# 输出结果：{1: 0, 2: 1, 3: 2, 4: inf}

注意事项 #

如果你调用方法时传入了cutoff参数限制最大路径长度，那么距离超过阈值的可达节点同样不会出现在返回结果中，需要和真正不可达的节点做区分。

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