Networkx кратчайший алгоритм дерева

Question

У меня есть ненаправленный взвешенный граф G с набором узлов и взвешенных ребер.

Я хочу знать, если есть способ, реализованный в NetworkX найти минимального остовного дерева в графе между заданными узлами (например nx.steiner_tree (G, [ «Берлин», «Киль», «Munster» , 'Nurnberg'])) (по-видимому, их нет?)

У меня нет точек репутации для отправки изображений. Ссылка на подобным же образом может быть: Map (A3, C1, C5, E4)

Что я имею в виду:

1. проверки dijkstras кратчайших путей между всеми узлами назначения;
2. поместить все узлы (промежуточные и получатели) и ребра на новый граф V;
3. вычислить mst на V (для удаления циклов путем разбиения самого длинного края);

Может быть, есть лучшие способы (corectness- and computation-wise)? Потому что этот подход довольно плох с тремя узлами назначения и становится лучше с большим количеством узлов.

P.S. Мой график плоский (его можно нарисовать на бумаге так, чтобы ребра не пересекались). Может быть, может помочь какой-то метод весны/силы (как в d3-визуализации)?

Answer 1

Насколько я понимаю ваш вопрос, вы пытаетесь найти компонент с наименьшим весом, содержащий набор узлов. Это проблема Steiner tree in graphs. Это NP полный. Вероятно, вам лучше всего взять какую-то эвристику, основанную на конкретном случае, который вы изучаете.

Для двух узлов подход к этому - это алгоритм Дейкстры - это самый быстрый, если вы расширяете оба узла до тех пор, пока не пересекаются две оболочки. Для трех узлов я подозреваю, что версия алгоритма Дейкстры, где вы расширяетесь вокруг каждого из узлов, даст хорошие результаты, но я не вижу, как убедиться, что вы получаете лучшее.

Я нашел another question для этого, у которого есть несколько достойных ответов (размещенный вопрос имел невзвешенный график, поэтому он отличается, но алгоритмы, приведенные в ответах, подходят для взвешивания). Есть некоторые хорошие, выходящие за рамки только принятого ответа.

Answer 2

В networkx имеется стандартный алгоритм Крускаля, реализованный с неориентированным взвешенным графом в качестве входного. Эта функция называется «minimum_spanning_tree»

Я предлагаю вам построить подграф, содержащий нужные вам узлы, а затем запустить алгоритм Крускаля.

import nertworkx as nx 
H=G.subgraph(['Berlin','Kiel', 'Konstanz']) 
MST=nx.minimum_spanning_tree(H)