CODEWITHSUNDEEP
pythonpython-3.xgraphnetworkx
Peter.k
Peter.k

Reputation: 1548

How to find shortest path in networkx without searchning back?

I have typical graph, it's a tree and I can find shortest path between two nodes:

nx.shortest_path(G, source=root, target=target)

But I don't know if there's a simple function which would disallow to search backwards. So namely, as input is:

nx.shortest_path(G, 5, 10)

[5, 6, 10]

it's looking forward (down the tree), but if

nx.shortest_path(G, 5, 3)

[5, 3]

it returns up the tree but should give None.

My question is: is there any simple way to get out or I just need to implement a custom function to check for this issue?

Upvotes: 0

Views: 1386

Answers (1)

Mykola Zotko
Mykola Zotko

Reputation: 17824

As mentioned in comments there is no "up" or "down" in a graph. You can create a directed graph using the class DiGraph(), where you get the error "NetworkXNoPath: No path between 3 and 1.", when you try to find the path against edge directions. In this case you can use try to catch the exception:

import networkx as nx
from networkx import NetworkXNoPath

G = nx.DiGraph([(1, 2), (2, 3), (4,2)]) # create a directed graph

nx.shortest_path(G, source=1, target=3)
# [1, 2, 3]

try:
    path = nx.shortest_path(G, source=3, target=1)
except NetworkXNoPath:
    path = None

Alternatively you can check if two vertices have any path at all:

nx.has_path(G, source=3, target=1)
# False

if nx.has_path(G, source=3, target=1):
    path = nx.shortest_path(G, source=3, target=1)
else:
    path = None

Directed Graph

Upvotes: 1

Related Questions