Рассмотрим задачу нахождения минимального веса связное подмножество Т ребер из взвешенного связного графа G. Вес T представляет собой сумму всех краевых весов в Т. (a) Почему эта проблема не только проблема минимального связующего дерева? Подсказка: думаю отрицательный вес края. (б) Дайте эффективный алгоритм для вычисления минимального веса связного подмножества Т.минимальный вес связное подмножество Т алгоритма ребер
(с) от Sciena Manual
(а) связующее дерево минимизирует краткое дерево веса, но minimum weight connected subset - каждая пару веса пути, поэтому мы можем использовать одни и те же отрицательные ребра для уменьшения каждого пути пары?
(b) решение на лбу: выполнить alg n раз dijkstra, отслеживать предыдущие пары кратчайшими путями. Кажется, не самая лучшая, другая идея - сортировать все ребра и происходит от самого большого - попытаться удалить каждый и проверить подключение ...
В чем ваш вопрос? Мы не собираемся делать домашнее задание для вас! – templatetypedef
Я не думаю, что поиск кратчайших путей будет работать. Выбранные ребра необязательно должны формировать простой путь между двумя узлами. Например: '1 - 2 (-1); 2 - 3 (-2); 2 - 4 (-4) ': вы должны выбрать все ребра, но они не образуют путь. Поэтому я не думаю, что это связано с путями, по крайней мере, не очень очевидным образом. – IVlad
Я не мог разобрать ваш ответ для (a). Не могли бы вы уточнить? – Ishtar