Вопрос по algorithm, graph, data-structures, minimum-spanning-tree – Минимальное остовное дерево боится отрицательных весов?

33

Это дополнительный вопросПочему большинство графовых алгоритмов не так легко адаптируются к отрицательным числам?.

Я думаю, что Shortest Path (SP) имеет проблему с отрицательными весами, потому что он складывает все веса вдоль путей и пытается найти минимальный.

Но я не думаю, что у Minimum Spanning Tree (MST) есть проблемы с отрицательными весами, потому что он принимает только один край минимального веса, не заботясь об общем общем весе.

Я прав?

Кстати, когда все ребра в графе отрицательны, поиск кратчайшего пути является той же проблемой, что и поиск самого длинного пути для графа с ребрами, помеченными абсолютным значением их исходной длины. Известно, что проблема длинного пути является NP-трудной. Palec

Ваш Ответ

3   ответа
-3

Алгоритм prim работает подобно алгоритму Дейкстры, но в алгоритме prim он не должен вычислять кратчайший путь от i до j, имеющий отрицательные ребра. Таким образом, их другой алгоритм - это их алгоритм Беллмана-Форда для вычисления кратчайшего пути от i до j с отрицательным фронтом.

Следовательно, алгоритм Прима и Крускала не боится отрицательных граней.

1

вы правы, потому что если вы видите алгоритм для кратчайшего пути, как у дикстера, он проверит, больше ли текущее расстояние вершины v, чем сумма текущего значения + вес ребра, тогда он изменит значение расстояния вершины v от s на значение суммы, и если вес ребра отрицателен, то это создаст некоторые проблемы.

Но в задаче MST есть алгоритмы типа простых чисел, kruskal, которые принимают только край минимального веса, чтобы отрицательный край соответствовал MST.

50

х популярных алгоритма нахождения MST (Kruskal 's и Prim' s) отлично работают с отрицательными ребрами.

На самом деле, вы можете просто добавить большую положительную константу ко всем ребрам вашего графа, делая все ребра положительными. MST (как подмножество ребер) останется прежним.

Два самых популярных алгоритма нахождения MST (Kruskal 's и Prim' s) отлично работают с отрицательными ребрами, потому что они работают на неориентированных графах.
Тот факт, что дерево, являющееся подграфом графа, имеет фиксированное число ребер в зависимости от количества вершин, поэтому добавление числаp к каждому ребру стоимость увеличивает общую стоимость MSTpE, Это неверно при поиске кратчайшего пути, потому что кратчайшие пути могут состоять из разного числа ребер.

Похожие вопросы