CODEWITHSUNDEEP
pythonnetworkx
Vincenzo Lavorini
Vincenzo Lavorini

Reputation: 2116

Finding N shortest paths in a graph

I need to find the N shortest path between two nodes. As example, the following code create three nodes and four edges, and the two shortest paths are (1, 3) and (1, 2, 3)

import networkx as nx

G = nx.MultiDiGraph()
G.add_edge(1, 2, **{'weight': 15, 'max': 3})
G.add_edge(1, 3, **{'weight': 30, 'max': 4})
G.add_edge(2, 3, **{'weight': 20, 'max': 3})
G.add_edge(2, 3, **{'weight': 20, 'max': 5})

Is there a method in NetworkX to find them?

I'm aware of the method nx.all_shortest_paths(rete,1, 3, weight='weight'), but in cases like this one the method returns only the shortest path, (1,3).

Thank you!

Upvotes: 0

Views: 1999

Answers (1)

ales_t
ales_t

Reputation: 2017

From the documentation, it looks like you can generate all simple paths between two vertices starting from the shortest paths with shortest_simple_paths:

https://networkx.github.io/documentation/stable/reference/algorithms/generated/networkx.algorithms.simple_paths.shortest_simple_paths.html#

Edit: answer for multigraphs

This is a very crude solution to get the answer you're looking for. I assume it will only work well for small graphs:

G = nx.MultiDiGraph()
G.add_edge(1, 2, **{'weight': 15, 'max': 3})
G.add_edge(1, 3, **{'weight': 30, 'max': 4})
G.add_edge(2, 3, **{'weight': 20, 'max': 3})
G.add_edge(2, 3, **{'weight': 20, 'max': 5})

# get all paths and convert them to tuples so that we can
# deduplicate them
paths = [tuple(p) for p in nx.all_simple_paths(G, 1, 3)]

# sort the paths according to the number of nodes in the path
print(sorted(set(paths), key=lambda x:len(x)))

Edit 2: answer for weighted multigraphs

This is a bit more complicated, you need to write your own "path score" function and pass it to the sorter.

G = nx.MultiDiGraph()
G.add_edge(1, 2, **{'weight': 15, 'max': 3})
G.add_edge(1, 3, **{'weight': 30, 'max': 4})
G.add_edge(2, 3, **{'weight': 20, 'max': 3})
G.add_edge(2, 3, **{'weight': 20, 'max': 5})


def get_edge_weight(u, v):
    """Return the minimum weight of all edges between nodes u and v."""
    return min([e['weight'] for e in G.get_edge_data(u, v).values()])


def weighted_path_score(path):
    """Sum of edge weights in path."""
    edges = zip(path, path[1:])
    return sum(get_edge_weight(u, v) for u, v in edges)


paths = [tuple(p) for p in nx.all_simple_paths(G, 1, 3)]

# sort using the weighted path score
print(sorted(set(paths), key=weighted_path_score))

You can play around with edge weights and check that the order of returned paths respects it (e.g. setting a high weight to edge 1-3 will result in the path (1,2,3) being listed first).

Upvotes: 3

Related Questions