Нахождение N кратчайших путей в графе

Question

Мне нужно найти кратчайший путь N между двумя узлами. Например, следующий код создает три узла и четыре ребра, и два самых коротких пути равны (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})

Есть ли в NetworkX метод для их поиска?

Мне известен метод nx.all_shortest_paths(rete,1, 3, weight='weight'), но в подобных случаях метод возвращает только кратчайший путь, (1,3).

Спасибо!

Answer 1

Из документации видно, что вы можете сгенерировать все простые пути между двумя вершинами, начиная с самых коротких путей с помощью shortest_simple_paths:

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

Редактировать: ответить на мультиграфы

Это очень грубое решение, чтобы получить ответ, который вы ищете.Я предполагаю, что это будет хорошо работать только для небольших графиков:

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)))

Редактировать 2: ответ для взвешенных мультиграфов

Это немного сложнее, вам нужно написать свой собственный "счет пути"функции и передать его сортировщику.

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))

Вы можете поиграться с весами ребер и проверить, что порядок возвращаемых путей учитывает их (например, установка большого веса для ребра 1-3 приведет к пути(1,2,3) быть первым в списке).