Найти минимальный вес связующего дерева в неориентированном графе, где есть отрицательные ребра

Question

Поэтому мне нужно решить этот график, у меня есть общее представление о том, как его решить, но если я делаю это неправильно, пожалуйста, поправьте меня.

Поэтому, чтобы найти MST, мне нужно выполнить алгоритм Крускала на графе.

вот мой psuedocode для этого алгоритма Kruskals

Крускал (V,E) A = ноль; для каждого v содержит в V сделать непересекающимся множество (v) Сортировать E по весу все больше для каждого (v1, v2) содержится в E, если

 Крускала (V, E)
A = ноль; для каждого v, содержащегося в V, создайте непересекающееся множество (v) Сортируйте E по весу все больше для каждого (v1, v2), содержащегося в E, если Find(v1) не равно Find(v2)
          A = A Union {(v1,v2)}
          Union(v1,v2)
Return A

Итак, первое, что я делаю, это нахожу узлы с кратчайшими расстояниями, верно?

1)

Я предполагаю, что расстояние от S до H кратчайшее, так как d(h,s) = -3

так что A = {(ч, с)}

так что теперь мы следуем этой схеме

2) A = {(h, s), (s, f)}

3) A = {(h, s), (s, f) (s, n)}

4) A = {(h, s) (s, f) (s, n) (f, k)}

5) A = {(h, s) (s, f) (s, n) (f, k) (s, m)} (мы пропускаем H к N, потому что путь от h к n уже сделан, который проходит через с)

6) A = {(h, s) (s, f) (s, n) (f, k) (s, m) (d, b)}

7) A = {(h, s) (s, f) (s, n) (f, k) (s, m) (d, b) (b, m)}

так что теперь, так как есть путь, который соединяет все ребра, мы хороши, верно?

но я не понимаю, что есть расстояние [u,v], которое короче пути [u,v] через несколько вершин. Например, d[d,m] короче, чем p[d,m], который сначала проходит через B. Я делаю что-то неправильно?

Answer 1

Вы не делаете ничего плохого. Нет гарантии, что MST сохраняет кратчайшие расстояния между узлами. Например: три узла полного графа ABC с весами ребер 3, 2, 2 (с извинениями за мой ascii art):

A --- 2 --- B
|           |
2          /
|         /
C----3---/ 

Минимальное связующее дерево - это CAB, но расстояние между B и C в исходном графе равно 3, а в MST 4.