[Python图论]在用图nx.shortest_path求解最短路径时,节点之间有多条边edge,会如何处理?

本文主要是介绍[Python图论]在用图nx.shortest_path求解最短路径时,节点之间有多条边edge,会如何处理?,希望对大家解决编程问题提供一定的参考价值,需要的开发者们随着小编来一起学习吧!

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

# 输出图G各节点之间有多少条边edge,并给出其长度
Edges between 103928 and 25508583:共2条
Edge: 103928 -> 25508583, Key: 0, Length: 77.277
Edge: 103928 -> 25508583, Key: 1, Length: 112.16900000000001
Edges between 26630792 and 5521427550:共2条
Edge: 26630792 -> 5521427550, Key: 0, Length: 85.091
Edge: 26630792 -> 5521427550, Key: 1, Length: 88.07600000000001
Edges between 107876 and 107873:共2条
Edge: 107876 -> 107873, Key: 0, Length: 83.102
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 属性,并选择长度最短的那条路径作为该节点对之间的最短路径。
  • 这个过程会在整个图上进行,直到找到从起点到终点的全局最短路径。

具体示例

以你的数据为例:

  1. 节点 103928 -> 25508583:

    • 第一条路径长度:77.277
    • 第二条路径长度:112.169
    • NetworkX 选择:77.277 长度的路径(Key: 0)
  2. 节点 26630792 -> 5521427550:

    • 第一条路径长度:85.091
    • 第二条路径长度:88.076
    • NetworkX 选择:85.091 长度的路径(Key: 0)
  3. 节点 107876 -> 107873:

    • 第一条路径长度:83.102
    • 第二条路径长度:186.669
    • NetworkX 选择:83.102 长度的路径(Key: 0)
  4. 节点 11767210 -> 12026764:

    • 第一条路径长度:219.545
    • 第二条路径长度:95.666
    • NetworkX 选择:95.666 长度的路径(Key: 1)

总结

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

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

# 输出图内各节点之间的边及其长度import networkx as nx# Get all the nodes in the graph
nodes = G.nodes()# Iterate over all pairs of nodes
for u in nodes:for v in nodes:# Skip if u and v are the same nodeif u == v:continue# Get the edges between u and vedges = G.get_edge_data(u, v)# If there are no edges between u and v, skip to the next pair of nodesif edges is None:continueedges_count = len(edges.items())if edges_count >1:# Print the edges and their lengthsprint(f"Edges between {u} and {v}:共{edges_count}条")for key, data in edges.items():print(f"Edge: {u} -> {v}, Key: {key}, Length: {data['length']}")

 

这篇关于[Python图论]在用图nx.shortest_path求解最短路径时,节点之间有多条边edge,会如何处理?的文章就介绍到这儿,希望我们推荐的文章对编程师们有所帮助!



http://www.chinasem.cn/article/1127179

相关文章

Python实现特殊字符判断并去掉非字母和数字的特殊字符

《Python实现特殊字符判断并去掉非字母和数字的特殊字符》在Python中,可以通过多种方法来判断字符串中是否包含非字母、数字的特殊字符,并将这些特殊字符去掉,本文为大家整理了一些常用的,希望对大家... 目录1. 使用正则表达式判断字符串中是否包含特殊字符去掉字符串中的特殊字符2. 使用 str.isa

python中各种常见文件的读写操作与类型转换详细指南

《python中各种常见文件的读写操作与类型转换详细指南》这篇文章主要为大家详细介绍了python中各种常见文件(txt,xls,csv,sql,二进制文件)的读写操作与类型转换,感兴趣的小伙伴可以跟... 目录1.文件txt读写标准用法1.1写入文件1.2读取文件2. 二进制文件读取3. 大文件读取3.1

使用Python实现一个优雅的异步定时器

《使用Python实现一个优雅的异步定时器》在Python中实现定时器功能是一个常见需求,尤其是在需要周期性执行任务的场景下,本文给大家介绍了基于asyncio和threading模块,可扩展的异步定... 目录需求背景代码1. 单例事件循环的实现2. 事件循环的运行与关闭3. 定时器核心逻辑4. 启动与停

基于Python实现读取嵌套压缩包下文件的方法

《基于Python实现读取嵌套压缩包下文件的方法》工作中遇到的问题,需要用Python实现嵌套压缩包下文件读取,本文给大家介绍了详细的解决方法,并有相关的代码示例供大家参考,需要的朋友可以参考下... 目录思路完整代码代码优化思路打开外层zip压缩包并遍历文件:使用with zipfile.ZipFil

Python处理函数调用超时的四种方法

《Python处理函数调用超时的四种方法》在实际开发过程中,我们可能会遇到一些场景,需要对函数的执行时间进行限制,例如,当一个函数执行时间过长时,可能会导致程序卡顿、资源占用过高,因此,在某些情况下,... 目录前言func-timeout1. 安装 func-timeout2. 基本用法自定义进程subp

Python实现word文档内容智能提取以及合成

《Python实现word文档内容智能提取以及合成》这篇文章主要为大家详细介绍了如何使用Python实现从10个左右的docx文档中抽取内容,再调整语言风格后生成新的文档,感兴趣的小伙伴可以了解一下... 目录核心思路技术路径实现步骤阶段一:准备工作阶段二:内容提取 (python 脚本)阶段三:语言风格调

Python结合PyWebView库打造跨平台桌面应用

《Python结合PyWebView库打造跨平台桌面应用》随着Web技术的发展,将HTML/CSS/JavaScript与Python结合构建桌面应用成为可能,本文将系统讲解如何使用PyWebView... 目录一、技术原理与优势分析1.1 架构原理1.2 核心优势二、开发环境搭建2.1 安装依赖2.2 验

一文详解如何在Python中从字符串中提取部分内容

《一文详解如何在Python中从字符串中提取部分内容》:本文主要介绍如何在Python中从字符串中提取部分内容的相关资料,包括使用正则表达式、Pyparsing库、AST(抽象语法树)、字符串操作... 目录前言解决方案方法一:使用正则表达式方法二:使用 Pyparsing方法三:使用 AST方法四:使用字

Java字符串处理全解析(String、StringBuilder与StringBuffer)

《Java字符串处理全解析(String、StringBuilder与StringBuffer)》:本文主要介绍Java字符串处理全解析(String、StringBuilder与StringBu... 目录Java字符串处理全解析:String、StringBuilder与StringBuffer一、St

Python列表去重的4种核心方法与实战指南详解

《Python列表去重的4种核心方法与实战指南详解》在Python开发中,处理列表数据时经常需要去除重复元素,本文将详细介绍4种最实用的列表去重方法,有需要的小伙伴可以根据自己的需要进行选择... 目录方法1:集合(set)去重法(最快速)方法2:顺序遍历法(保持顺序)方法3:副本删除法(原地修改)方法4: