Это следующий вопрос Почему большинство алгоритмов графов не так легко адаптируются к отрицательным числам?.
Я думаю, что Shortest Path (SP) имеет проблему с отрицательными весами, поскольку он суммирует все веса по путям и пытается найти минимальный.
Но я не думаю, что Минимальное Spanning Tree (MST) имеет проблемы с отрицательными весами, потому что он просто берет единый минимальный край веса, не заботясь об общем суммарном весе.
Я прав?
Да, вы правы. Концепция MST допускает веса произвольного знака. Два самых популярных алгоритма для поиска MST (Kruskal и Prim's) отлично работают с отрицательными ребрами.
На самом деле вы можете просто добавить большую положительную константу ко всем краям вашего графика, сделав все ребра положительными. MST (как подмножество ребер) останется неизменным.
Да, вы правы, потому что, если вы видите алгоритм для кратчайшего пути, например, dijkstera, он проверит, превышает ли нынешнее расстояние вершины v сумму текущего значения + вес края, тогда он изменит значение расстояния до вершины v от s на величину суммы, и если вес края отрицательный, тогда он даст некоторые проблемы.
Но в задаче MST существуют такие алгоритмы, как примитивы, kruskal, которые берут только край минимального веса, чтобы сделать отрицательный фронт подходящим для MST.