MST a najkrótsza ścieżka.

Question

Mam pytanie z teorii grafów. Czy jak policzę sobie minimalne drzewo rozpinające (MST) dla pewnego grafu to czy to oznacza, że są w tym drzewie zawarte najkrótsze możliwe ścieżki od pewnego wierzchołka tego grafu do pozostałych?

Answer 1

Nie przerabiałem jeszcze MTS, ale po szybkiej analizie kilku minimalnych drzew rozpinających mogę stwierdzić, że nie. Widać to dobrze na tym przykładzie:

http://algorytmika.wikidot.com/mst

Pozdrawiam!