NetworkX中获取所有节点对全部最短路径的问题求助

单条最短路径返回的原因 #

nx.all_pairs_shortest_path()的设计目标是快速获取每对节点的任意一条最短路径，内部实现BFS遍历时，仅会记录每个目标节点首次被访问到的路径，不会存储相同长度的其他可达路径，因此只会返回单条结果，符合你遇到的现象。

解决建议 #

• 方法1：直接使用NetworkX内置的全量最短路径接口
  针对无权图的全最短路径查询需求，NetworkX专门提供了nx.all_pairs_shortest_paths()接口，是你当前使用的单条最短路径接口的全量版本，调用方式和原有接口完全兼容，会返回每对节点之间所有长度相同的最短路径，示例代码如下：

  import networkx as nx
  # 初始化你的无向无权图（此处省略你自己的图构建逻辑）
  G = nx.Graph()
  G.add_edges_from([(1,2), (2,3), (1,3), (3,4)]) # 示例边
  # 计算所有节点对的所有最短路径，返回结果是字典格式，键为源节点，值为目标节点到路径列表的映射
  all_sp = dict(nx.all_pairs_shortest_paths(G))
  # 示例：查看节点1到节点3的所有最短路径，输出为[[1,2,3], [1,3]]
  print(all_sp[1][3])
  

  如果你不需要全节点对的结果，仅需要查询特定源节点到所有目标、或者特定两节点之间的所有最短路径，可以分别使用更轻量化的nx.single_source_shortest_paths()、nx.all_shortest_paths()接口，减少不必要的计算开销。
  注意：如果你的图规模较大，且部分节点对之间存在指数级数量的最短路径，该类接口的内存占用和耗时会显著上升，建议根据实际需求做范围裁剪。
• 方法2：自定义BFS实现全量最短路径统计
  如果你有定制化的过滤、统计需求，可以自行实现BFS逻辑：遍历过程中为每个节点维护所有能以最短距离到达该节点的前驱节点集合，遍历完成后通过回溯前驱节点集合生成所有可能的最短路径，这种方式可以灵活适配特殊业务逻辑。

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