NetworkX中Dijkstra算法使用None权重作为隐藏边失败问题排查

我尝试通过权重函数限制最短路径遍历仅针对特定交通模式：若边为可通行类型则分配对应权重，否则返回None（文档称None权重会使边被隐藏，遍历将忽略）。但实际操作中出现异常：尽管nx.has_path确认存在路径，使用single_source_dijkstra并传入此类权重时却无法找到路径。

已知条件 #

• 在集成多模态网络和孤立道路网络中，以下代码均返回True：

  nx.has_path(fullNetwork,orig,dest)
  nx.has_path(roadNetwork,orig,dest)
  

• 在道路网络中，无权重及使用'walkTime'权重的single_source_dijkstra调用均能正常返回时间和路径：

  roadTime,roadPath = nx.single_source_dijkstra(roadNetwork, source=orig, target=dest)
  

  roadTime,roadPath = nx.single_source_dijkstra(roadNetwork, source=orig, target=dest, weight='walkTime')
  

• 所有道路边的'walkTime'均为正浮点值，其他交通模式无该值。

尝试的方法及报错 #

1. 定义权重函数仅使用道路边的walkTime：

   def roadWalkTime(u,v,attr):
       if attr.get('modality','poo') == 'road':
           return attr.get('walkTime',None)
       else:
           return None
   
   roadTime,roadPath = nx.single_source_dijkstra(fullNetwork, source=orig, target=dest, weight=roadWalkTime)
   

   抛出错误：

   File C:\miniforge3\envs\GAT\lib\site-packages\networkx\algorithms\shortest_paths\weighted.py:747 in multi_source_dijkstra
       raise nx.NetworkXNoPath(f"No path to {target}.") from err
   
   NetworkXNoPath: No path to destin_0.
   

2. 定义静态权重属性：

   for u,v,attr in fullNetwork.edges(data=True):
       coreNetwork[u][v]['roadWalkTime'] = attr['walkTime'] if attr.get('modality','blah')=='road' else None
   

   使用该静态权重调用single_source_dijkstra仍报错；即使在孤立道路网络中，使用'roadWalkTime'权重调用失败，但使用'walkTime'则正常。

核心问题 #

NetworkX的Dijkstra类加权最短路径算法不支持权重为None的边。文档中提到的"隐藏边"仅适用于无权重的路径查找逻辑，加权算法要求权重必须是可比较的数值类型，None会被视为无效值，直接导致算法无法识别这条边的连通性，最终中断路径查找。

可行解决方法 #

1. 权重函数返回极大值而非None
   将非道路边的权重设为一个远大于正常路径总权重的数值（如1e10），这样算法会自动忽略这些高代价的边，同时保证所有边都有合法的数值权重：

   def roadWalkTime(u,v,attr):
       if attr.get('modality','poo') == 'road':
           return attr.get('walkTime', 1e10)
       else:
           return 1e10
   

2. 预先提取道路子图再计算
   直接从全网络中过滤出所有道路边生成子图，在子图上运行Dijkstra算法，这种方式更高效且逻辑更清晰：

   # 提取所有道路边构成子图
   road_subgraph = fullNetwork.edge_subgraph(
       [(u,v) for u,v,attr in fullNetwork.edges(data=True) if attr.get('modality') == 'road']
   )
   # 在子图上计算最短路径
   roadTime, roadPath = nx.single_source_dijkstra(road_subgraph, source=orig, target=dest, weight='walkTime')
   

3. 修正静态权重属性的赋值
   若坚持使用静态权重属性，需给非道路边赋极大值而非None：

   for u,v,attr in fullNetwork.edges(data=True):
       if attr.get('modality','blah') == 'road':
           fullNetwork[u][v]['roadWalkTime'] = attr['walkTime']
       else:
           fullNetwork[u][v]['roadWalkTime'] = 1e10
   

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