Skip to content
Advertisement

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

first of all I am really new to python in genereal and espcially to networkx. I got a question regarding the networkx shortest_path(G,source,target) function. For a series of found positions (let´s call them x), I would like to find the shortest path to another series of found positions (let´s call them y). I would like to find the shortest path for every x to only one of the points in y, namely the point that has the smallest length. So if x has two y´s in reach and the length (shortest_path_length(G,source,target)) for the first path is 5 and the path for the second is 10, I would like to only take the path with length 5 and safe the positions of all nodes for this path in a list and ignore the other paths.

I am using a skeletonized structure to do so. I am looking for dead ends (which is x, with degree == 1) and junctions (which is y, with degree >= 3)

I tried it with for loops, but did not work correct. My source would be x (deadends) and my target would be the closest y position (junction) I asked another question here, where my problem and part of the code is already written down. I will include a link, so that I do not flood this question with the same code again. Thank you to everyone helping me out.

Finding dead ends in a skeletonized canal structure

Advertisement

Answer

You can compute all shortest paths from a given source with nx.single_source_shortest_paths. You then just need to filter the results looking for paths to branchpoints, and then select the shortest of those.

#!/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()

This yields:

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]

enter image description here

User contributions licensed under: CC BY-SA
3 People found this is helpful
Advertisement