Учитывая неориентированный взвешенный граф G = (V, E). Каждая вершина представляет собой город и вес связанного края a, а b - количество лет, которое потребуется, чтобы закончить строительство высокоскоростного маршрута между городом a и городом b. Опишите алгоритм, который найдет наименьшее количество лет, прежде чем вы сможете путешествовать между любыми двумя городами на графике. Маршруты строятся одновременно, так что, если у нас есть три города a, b и c и край между a и b с весом 1, другое ребро между b и c с весом 2, тогда выход должен быть равен 2.Как я могу это решить?
ответ
Комментарий выше указывает на правильный ответ, по-моему, это звучит как классическая проблема алгоритма Прима. http://en.wikipedia.org/wiki/Prim's_algorithm
Как это? вы можете быть более конкретным, пожалуйста? например, просто использовал бы prims для поиска минимального остовного дерева, а затем вернул бы наибольший вес всех ребер в mst-работе? если да, то как вы могли бы доказать правильность алгоритма? –
@AdenDong Я бы сделал это так, как вы сказали. Если строительство железных дорог происходит одновременно, то минимальное остовное дерево будет математически давать вам оптимальные маршруты, которые необходимо построить для подключения всех узлов в сети. Самая длинная дуга между двумя вершинами на вашем пути между А и В должна заключаться в том, сколько вам придется ждать, чтобы путешествовать. –
- 1. Scapy error! Как я могу это решить?
- 2. Как я могу решить это предупреждение Java?
- 3. Объект просочился: Как я могу это решить?
- 4. StackOverflowError Как я могу это решить?
- 5. Как я могу решить это упражнение SQL?
- 6. Как я могу решить это правило сонара?
- 7. XBAP, System.Security.SecurityException, как я могу это решить?
- 8. Как я могу решить это в jsp?
- 9. Многомерный массив, как я могу это решить?
- 10. Что это за ошибка? Как я могу это решить?
- 11. Почему это происходит? Как я могу это решить?
- 12. Я не могу решить это в java
- 13. prepareForSegue не работает быстро. Как я могу это решить?
- 14. Расчет зрелости в MATLAB. Как я могу это решить?
- 15. Неопределенная ошибка индекса, как я могу это решить?
- 16. Как я могу решить это с помощью метапрограммирования?
- 17. как я могу это решить? ключевое слово не поддерживается 'datasource'
- 18. Синтаксическая ошибка Mysql. Как я могу это решить?
- 19. К сожалению, MyApp остановился. Как я могу это решить ...?
- 20. SetText не меняет TextView, как я могу это решить?
- 21. Ошибка планировщика заданий 0X1 Как я могу это решить?
- 22. Как я могу решить это три уравнения переменной с C#?
- 23. Макет, дублированный фрагментом и активностью. как я могу это решить?
- 24. Как я могу решить это математическое уравнение в PHP?
- 25. проблемы с потоком, как я могу это решить?
- 26. Как я могу решить это, возможно, используя целочисленное линейное программирование?
- 27. document.writeln() нарушает частичное обновление jQuery. Как я могу это решить?
- 28. Как я могу решить это регулярное выражение, Python?
- 29. Как я могу решить это исключение «нельзя исключить»?
- 30. Java абстрактный класс - как я могу лучше всего это решить?
Что вы пробовали? Подсказка: http://en.wikipedia.org/wiki/Kruskal%27s_algorithm – nhahtdh
просто использовал бы prims или kruskal для поиска минимального остовного дерева, а затем вернул бы наибольший вес всех ребер в mst-работе? если да, то как вы могли бы доказать правильность алгоритма? –
Для Kruskal доказательство довольно простое, так как вы всегда считаете наименьший край первым при добавлении. Я не уверен в том, что касается Прима, но это, вероятно, доказуемо. – nhahtdh