so, ich glaube jetzt ist mir doch noch die erleuchtung gekommen:
du muszt ja den _ganzen_ graphen betrachten und nicht, wie auch ich faelschlich angenommen habe, immer 2 punkte. und dann bist du mit MST, sprich kruskal, richtig dran.
nehmen wir dein beispiel mit den gewichten {a,b,c}={2,4,5}. zwischen "AC" bist du mit "5" minimaler als mit mit "6" ("ACB"). wenn du aber _von jedem_ knoten _zu jedem_ willst, dann stimmt der MST mit den kannten "ab" als spanning tree schon.
"ab":
AB: 6
AC: 4
BC: 2
SUM: 12
nimmt du jetzt von mir aus
"ac":
AB: 5 //juhu, gewinn
AC: 7
BC: 2
SUM: 14