Алгоритмы планирования NetworkX с мультиграфами: выражают пути как последовательность ребер (вместо узлов)? ⇐ Python

[Anonymous]

Я использую NetworkX для запуска алгоритмов планирования пути на мультиграфах. NetworkX выражает пути решения как последовательности узлов. Это представление неоднозначно для мультиграфов, поскольку соседние узлы могут быть соединены двумя или более ребрами; неясно, какие ребра являются частью решения.
Я могу вручную перебирать путь решения и искать ребро, которое является частью решения, на каждом этапе пути, но это кажется беспорядочно/расточительно.
Есть ли способ заставить NetworkX выражать пути как последовательность ребер, а не как последовательность узлов? Или более элегантный способ выразить пути как последовательности ребер в мультиграфе?
Игрушечный пример:
Рассмотрим следующее (ненаправленное ) график. Это мультиграф, поскольку вершины 1 и 2 соединены более чем одним ненаправленным ребром. Нас интересует путешествие от вершины 0 к вершине 2.


Реализация NetworkX:

Код: Выделить всё

import networkx as nx

edges = [
(0,1,0, {'cost': 3}),
(1,2,0, {'cost': 5}),
(1,2,1, {'cost': 10}),
]

G = nx.MultiGraph()
G.add_edges_from(edges)

total_cost, path = nx.single_source_dijkstra(G, source=0, target=2, weight='cost')
print(total_cost)  # 8
print(path)        # [0, 1, 2]

Показанный путь представляет собой только последовательность вершин вдоль решения, а не последовательность ребер. При переходе от вершины 1 к вершине 2 нет указания, какое ребро брать. Я могу выполнить поиск среди ребер между вершинами 1 и 2 и сохранить то, которое имеет наименьшую стоимость.
Эта процедура кажется тривиальной в игрушечной задаче, но становится раздражающе отнимающей много времени при планировании больших графики.

Подробнее здесь: https://stackoverflow.com/questions/791 ... ence-of-ed