如何仅使用 networkx (shortest_path) 获取最短路径

Question

首先，我对 python 总体来说是个新手，尤其是 networkx。我有一个关于 networkx shortest_path(G,source,target) 函数的问题。对于一系列找到的位置（我们称它们为 x），我想找到到另一系列找到的位置（我们称它们为 y）的最短路径。我想找到每个 x 到 y 中的一个点的最短路径，即具有最小长度的点。因此，如果 x 有两个 y 并且第一条路径的长度 (shortest_path_length(G,source,target)) 为 5，第二条路径的路径为 10，我只想采用长度为 5 的路径并确保位置安全列表中此路径的所有节点并忽略其他路径。

我正在使用骨架结构来这样做。我正在寻找死胡同（即 x，degree == 1）和路口（即 y，degree >= 3）

我用 for 循环试过，但没有正常工作。我的来源是 x（死角），我的目标是最近的 y 位置（连接点）我在这里问了另一个问题，我的问题和部分代码已经写下来了。我将包括一个 link，这样我就不会再次用相同的代码来淹没这个问题。谢谢大家帮助我。

Answer 1

您可以使用 nx.single_source_shortest_paths 计算来自给定源的所有最短路径。然后你只需要过滤结果寻找分支点的路径，然后 select 其中最短的。

#!/usr/bin/env python
"""
Find the shortest path between two sets of nodes of interest.
"""

import random
import networkx as nx

# create a reproducible test data set
random.seed(10)
g = nx.random_tree(15)

# determine the leaves and branchpoints
leaves = [node for node in g.nodes() if g.degree(node) == 1]
branchpoints = [node for node in g.nodes() if g.degree(node) > 2]

# find the shortest path from each leaf to any of the branchpoints
shortest_paths = dict() # leaf -> path
closest_branchpoint = dict() # leaf -> branchpoint
for leaf in leaves:
    # find paths to all other nodes
    paths_to_all_other_nodes = nx.single_source_shortest_path(g, leaf)
    # filter for paths to branchpoints
    paths_to_branchpoints = {node : path for node, path in paths_to_all_other_nodes.items() if node in branchpoints}
    # determine the closest branchpoint and save out branchpoint and corresponding path
    closest_branchpoint[leaf] = min(paths_to_branchpoints, key=lambda x: len(paths_to_branchpoints[x]))
    shortest_paths[leaf] = paths_to_branchpoints[closest_branchpoint[leaf]]

# print results
for leaf in leaves:
    print(f"{leaf} -> {closest_branchpoint[leaf]} : {shortest_paths[leaf]}")

# plot for visual confirmation
import matplotlib.pyplot as plt
from netgraph import Graph # pip install netgraph

Graph(g, node_layout='dot', node_labels=True, node_label_offset=0.05, node_label_fontdict=dict(size=20))
plt.show()

这产生：

1 -> 9 : [1, 9]
2 -> 0 : [2, 0]
5 -> 7 : [5, 6, 7]
8 -> 9 : [8, 9]
11 -> 13 : [11, 13]
12 -> 7 : [12, 7]
14 -> 13 : [14, 10, 4, 13]

如何仅使用 networkx (shortest_path) 获取最短路径

How to only get the shortest path with networkx (shortest_path)

python

networkx