K-кратчайшие пути с использованием пакета networkx в python

Question

Я создал мультидграф автострады Нидерландов, используя пакет osmnx.

График является мультидиграфом, возвращенным из osmnx. Поскольку мне интересно вычислить k-кратчайшие пути между источником и местом назначения, я попробовал библиотеку networkx. Тем не менее, networkx, похоже, не работает с мультидиграфом. Все, что я могу вычислить по кратчайшему пути.

Я хотел бы спросить, есть ли другой способ выполнить вычисление k-кратчайшего пути в python по мультидиграфу.

Answer 1

Попробуйте использовать команду networkx shortest_simple_paths ( документация).

Он возвращает генератор, который возвращает один путь за раз от кратчайшего до самого длинного.

G = nx.karate_club_graph()
X = nx.shortest_simple_paths(G, 0, 5)
k = 5
for counter, path in enumerate(X):
     print(path)
     if counter == k-1:
         break
> [0, 5]
> [0, 6, 5]
> [0, 10, 5]
> [0, 6, 16, 5]
> [0, 4, 6, 5]

Это будет работать с DiGraphс, но я не уверен насчет MultiDiGraph, Однако мне не ясно, что дорожная сеть будет MultiDiGraph.

Answer 2

Теперь у osmnx естьk_shortest_pathsметод, реализованный для мультидиграфа, вы можете использовать его следующим образом.

      ox.routing.k_shortest_paths(G, s, t, k)