Минимальное связующее дерево множества узлов в полном графе

Question

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

Мне нужно найти минимальное остовное дерево, охватывающее только точки, учитывая, что у меня есть координаты этих точек, и я могу найтидлина линий, которые их соединяют.

Какие-нибудь указатели или идеи о том, как это сделать?

Answer 1

Вы решаете проблему дерева Штейнера , которая является NP-сложной. networkx предоставляет алгоритм аппроксимации для решения этой проблемы: networkx.algorithms.approximation.steinertree.steiner_tree .