Найти минимальную стоимость среди узлов

Question

Предположим, у меня есть три пункта назначения A, B и C, и я сопоставляю стоимость поездки между A - B, B - A, A - C, C - A, B - C и C - B, и все они разные. Я должен искать конкретное место среди A, B и C, куда придут два других, и стоимость будет минимизирована. например, A и B могут прийти в местоположение C. И как это можно оптимизировать для N местоположения?

Answer 1

Я бы сказал, что эта проблема в O (| V | ^ {2}), и поэтому вам придется проверить стоимость поездки для каждого узла. Выберите узел, проверьте стоимость перемещения других n-1 узлов к этому узлу и сделайте это для каждого узла, поддерживая тот с наименьшей стоимостью перемещения.