Все кратчайшие пути для взвешенных графов с networkx?

Question

У меня есть график, составленный из двух разных наборов ребер. Первый набор составлен ребрами веса 1 (список 1). Второй набор составлен ребрами веса 2 (список 2). Сначала я создаю график с помощью networkx, а затем использую add_edges_from, чтобы добавить список 1 и список 2. Я хотел бы вычислить все кратчайшие пути в этом взвешенном графике. В основном я ищу аналог "all_shortest_paths", но с весами (похоже, что модуль "dijkstra" не позволяет вам узнать все возможные маршруты между данным источником и заданной целью). Если я пытаюсь использовать "all_shortest_path" с взвешенными ссылками (3 кортежа, два узла и вес), я получаю ошибку. Кто-нибудь может мне помочь? Большое спасибо!

Answer 1

Вот простой пример, чтобы показать, как работает all_shortest_paths()

import networkx as nx
import StringIO
edges = StringIO.StringIO("""
a b 1
a bb 1
b c 2
bb c 2
c d 1
a d 10""")
G = nx.read_weighted_edgelist(edges, nodetype=str)
print list(nx.all_shortest_paths(G, 'a', 'd', weight='weight'))
# [['a', 'b', 'c', 'd'], ['a', 'bb', 'c', 'd']]