CODEWITHSUNDEEP
pythonnetworkxshortest-path
BKS
BKS

Reputation: 2333

Max from a list of all shortest paths between two nodes

I have an undirected graph

I would like to calculate the max from a list of all the shortest path lengths between two nodes in the network, any ideas how I can do that?

Upvotes: 0

Views: 775

Answers (2)

jedwards
jedwards

Reputation: 30210

If you only want to consider some subset of vertices for source and target, you might do something like:

# Change these to fit your needs
sources = G.nodes()     # For example, sources = [0,1,4]
targets = G.nodes()

max_shortest_path = None
for (s,t) in itertools.product(sources, targets):
    if s == t: continue # Ignore
    shortest_paths = list(nx.all_shortest_paths(G, s, t))
    path_len = len(shortest_paths[0])
    if max_shortest_path is None or path_len > len(max_shortest_path[0]):
        max_shortest_path = list(shortest_paths)    # Copy shortest_paths list
    elif path_len == len(max_shortest_path[0]):
        max_shortest_path.extend(shortest_paths)

Afterward, max_shortest_path is a list. All elements of max_shortest_path are lists of equal length.

len(max_shortest_path[0]) will get you the length of the maximal shortest path in the graph.

The elements of max_shortest_path are the paths of this length.

Upvotes: 1

Aric
Aric

Reputation: 25289

I think you want the graph diameter which is the maximum of all-pairs shortest paths. https://networkx.github.io/documentation/latest/reference/generated/networkx.algorithms.distance_measures.diameter.html

Upvotes: 0

Related Questions