[Python图论]在用图nx.shortest_path求解最短路径时，节点之间有多条边edge ...

问： 在利用图求最短路径时，如果节点之间有多条路径，shortest_route = nx.shortest_path(G, source=start_node, target=end_node, weight='length')会如那里理，会自动选择最短那条吗？

1. # 输出图G各节点之间有多少条边edge,并给出其长度
2. Edges between 103928 and 25508583:共2条
3. Edge: 103928 -> 25508583, Key: 0, Length: 77.277
4. Edge: 103928 -> 25508583, Key: 1, Length: 112.16900000000001
5. Edges between 26630792 and 5521427550:共2条
6. Edge: 26630792 -> 5521427550, Key: 0, Length: 85.091
7. Edge: 26630792 -> 5521427550, Key: 1, Length: 88.07600000000001
8. Edges between 107876 and 107873:共2条
9. Edge: 107876 -> 107873, Key: 0, Length: 83.102
10. Edge: 107876 -> 107873, Key: 1, Length: 186.669

复制代码

答：是的，nx.shortest_path 会自动选择权重最小的那条路径。
当你在 NetworkX 中利用 nx.shortest_path(G, source=start_node, target=end_node, weight='length') 时，它会根据你指定的权重（在这个例子中是 'length'）找到源节点和目标节点之间权重最小的路径。
对于节点之间有多条路径的情况，NetworkX 会如下处理：

• 如果两个节点之间有多条路径，例如 (u, v)，NetworkX 会选择全部大概的路径，并根据你指定的权重属性（在这个例子中是 length）找到最小权重的路径。
  
• 在你的例子中，每一对节点之间都有两条路径。NetworkX 会比力这两条路径的 length 属性，并选择长度最短的那条路径作为该节点对之间的最短路径。
  
• 这个过程会在整个图上举行，直到找到从出发点到终点的全局最短路径。
  

具体示例

以你的数据为例：

• 节点 103928 -> 25508583:
  
  
  
  • 第一条路径长度：77.277
    
  • 第二条路径长度：112.169
    
  • NetworkX 选择：77.277 长度的路径（Key: 0）
    
  
  
• 节点 26630792 -> 5521427550:
  
  
  
  • 第一条路径长度：85.091
    
  • 第二条路径长度：88.076
    
  • NetworkX 选择：85.091 长度的路径（Key: 0）
    
  
  
• 节点 107876 -> 107873:
  
  
  
  • 第一条路径长度：83.102
    
  • 第二条路径长度：186.669
    
  • NetworkX 选择：83.102 长度的路径（Key: 0）
    
  
  
• 节点 11767210 -> 12026764:
  
  
  
  • 第一条路径长度：219.545
    
  • 第二条路径长度：95.666
    
  • NetworkX 选择：95.666 长度的路径（Key: 1）
    
  
  

总结

• NetworkX 的 shortest_path 函数会自动为你选择每对节点之间权重最小的路径。
  
• 因此，你不需要手动指定哪条路径是最短的，NetworkX 会基于权重（如 length）自动做出选择。
  

输出图内各节点之间的边及其长度 代码：

1. # 输出图内各节点之间的边及其长度
3. import networkx as nx
6. # Get all the nodes in the graph
7. nodes = G.nodes()
9. # Iterate over all pairs of nodes
10. for u in nodes:
11.     for v in nodes:
12.         # Skip if u and v are the same node
13.         if u == v:
14.             continue
16.         # Get the edges between u and v
17.         edges = G.get_edge_data(u, v)
18.         
19.         # If there are no edges between u and v, skip to the next pair of nodes
20.         if edges is None:
21.             continue
22.         edges_count = len(edges.items())
23.         if edges_count >1:
24.           # Print the edges and their lengths
25.           print(f"Edges between {u} and {v}:共{edges_count}条")
26.           for key, data in edges.items():
27.               print(f"Edge: {u} -> {v}, Key: {key}, Length: {data['length']}")

复制代码

 

免责声明：如果侵犯了您的权益，请联系站长，我们会及时删除侵权内容，谢谢合作！更多信息从访问主页：qidao123.com:ToB企服之家，中国第一个企服评测及商务社交产业平台。