Logo Questions Linux Laravel Mysql Ubuntu Git Menu
 

Networkx - Shortest path length

I'm using networkx to manage large network graph which consists of 50k nodes.

I want to calculate the shortest path length between a specific set of nodes, say N.
For that i'm using the nx.shortest_path_length function.

In some of the nodes from N there might not be a path so networkx is raising and stopping my program.

Is there any way to run this program without any error?
And to tell to shortest_path_length to return some maximum value?

Code simply uses nx.shortest_path_length(G,i,j)in loop. and error is as follows

raise nx.NetworkXNoPath("No path between %s and %s." % (source, target)) networkx.exception.NetworkXNoPath: No path between V and J

like image 735
username_4567 Avatar asked Feb 24 '12 11:02

username_4567


People also ask

How do I find the shortest path on NetworkX?

A* Algorithm Shortest paths and path lengths using the A* (“A star”) algorithm. Returns a list of nodes in a shortest path between source and target using the A* ("A-star") algorithm. Returns the length of the shortest path between source and target using the A* ("A-star") algorithm.

What is average shortest path length NetworkX?

The average shortest path length is the sum of path lengths d(u,v) between all pairs of nodes (assuming the length is zero if v is not reachable from v) normalized by n*(n-1) where n is the number of nodes in G. If True use edge weights on path.

Which method can be used to get the shortest path in NetworkX library?

Uses Dijkstra's Method to compute the shortest weighted path between two nodes in a graph. If this is a string, then edge weights will be accessed via the edge attribute with this key (that is, the weight of the edge joining u to v will be G.

How do you find the average shortest path length on a graph?

We can calculate average path length of a graph by using following formula: Here d(vi, vj) represents the length of shortest path exists between two vertices. So, we take sum of all shortest paths between all vertices and divide number of all possible paths.


1 Answers

import networkx as nx
G=nx.Graph()
G.add_nodes_from([1,2,3,4])
G.add_edge(1,2)
G.add_edge(3,4)
try:
    n=nx.shortest_path_length(G,1,4)
    print n
except nx.NetworkXNoPath:
    print 'No path'
like image 122
Peter de Rivaz Avatar answered Sep 30 '22 18:09

Peter de Rivaz