Как минимизировать путь прохождения полного графа и найти оптимальную начальную точку?

Question

Скажите, что N узлов и вес путей, соединяющих некоторые из этих узлов, вам даны. В среднем, узел направлен соединенным с m узлами, где m намного меньше N. Мне интересно знать, как выбрать начальную точку перемещения, учитывая, что мы должны покрыть все узлы с минимально возможной суммой веса пути. Кроме того, N - очень большое число (между 10k-50k).

Answer 1

Я бы сказал, грубая сила - это путь к go. Для данного графа G = (V, E) выберите каждую вершину v ε V, найдите общий вес от v до всех остальных узлов, используя простой поиск в ширину. Начните с v, go до всех смежных вершин, добавьте вес всех ребер и повторите. Повторите это, и вы получите минимум.