Рассмотрим проблему нахождения связного подмножества T минимального веса ребер из взвешенного связного графа G. Вес T является суммой всех весов ребер в T. (a) Почему эта проблема не просто минимальный охватпроблема дерева?Подсказка: подумайте о негативных весовых краях.(b) Дайте эффективный алгоритм для вычисления подмножества минимального веса, связанного с T.
(c) из Sciena Manual
(a) связующее дерево минимизирует суммарный вес дерева, но minimum weight connected subset - каждыйвес парного пути, поэтому мы можем повторно использовать одни и те же отрицательные ребра, чтобы уменьшить каждый парный путь?
(b) решение на лбу: выполнить alg n раз dijkstra, отслеживая кратчайшие пути предыдущих пар.Кажется, не самая лучшая, другая идея - сортировка всех ребер и переход от самого большого - попробуйте удалить каждый и проверить подключение ...