Как я могу это решить?

Учитывая неориентированный взвешенный граф G = (V, E). Каждая вершина представляет собой город и вес связанного края a, а b - количество лет, которое потребуется, чтобы закончить строительство высокоскоростного маршрута между городом a и городом b. Опишите алгоритм, который найдет наименьшее количество лет, прежде чем вы сможете путешествовать между любыми двумя городами на графике. Маршруты строятся одновременно, так что, если у нас есть три города a, b и c и край между a и b с весом 1, другое ребро между b и c с весом 2, тогда выход должен быть равен 2.Как я могу это решить?

источник

2012-06-01 Aden Dong

Что вы пробовали? Подсказка: http://en.wikipedia.org/wiki/Kruskal%27s_algorithm – nhahtdh

просто использовал бы prims или kruskal для поиска минимального остовного дерева, а затем вернул бы наибольший вес всех ребер в mst-работе? если да, то как вы могли бы доказать правильность алгоритма? –

Для Kruskal доказательство довольно простое, так как вы всегда считаете наименьший край первым при добавлении. Я не уверен в том, что касается Прима, но это, вероятно, доказуемо. – nhahtdh

Комментарий выше указывает на правильный ответ, по-моему, это звучит как классическая проблема алгоритма Прима. http://en.wikipedia.org/wiki/Prim's_algorithm

источник

2012-06-01 02:28:56

Как это? вы можете быть более конкретным, пожалуйста? например, просто использовал бы prims для поиска минимального остовного дерева, а затем вернул бы наибольший вес всех ребер в mst-работе? если да, то как вы могли бы доказать правильность алгоритма? –

@AdenDong Я бы сделал это так, как вы сказали. Если строительство железных дорог происходит одновременно, то минимальное остовное дерево будет математически давать вам оптимальные маршруты, которые необходимо построить для подключения всех узлов в сети. Самая длинная дуга между двумя вершинами на вашем пути между А и В должна заключаться в том, сколько вам придется ждать, чтобы путешествовать. –

ответ

Смежные вопросы