Minimaler Weg zw. zwei Punkten - MST?

natural_born_ch

Hallo Leute,

ich weiß nicht, ob das hier so reinpasst, aber ihr werdet dass dann hoffentlich verschieben, falls dem nicht so sein sollte

Folgende Aufgabenstellung:

Code

Sei G = (V,E) ein Graph mit einer Kantengewichtsfunktion c.
(a) Für je zwei Knoten u und v ist ein Weg von u nach v gesucht, so dass das maximale
Kantengewicht, das auf diesem Weg auftritt, möglichst klein ist. Zeigen Sie, dass dieses
Problem durch das Bestimmen eines MST in G gelöst werden kann.

Mit MST ist das hier gemeint.

Nun meine Frage: Stellt euch ein Dreieck vor mit den Kantengewichten 2, 4 und 5. Der kleinste Baum wird die Kanten 2 und 4 hervorbringen, der kürzeste Weg zw. den beiden Punkten wird aber durch die Strecke mit dem Gewicht 5 erreicht. Also kann man es doch gar nicht zeigen? ... Oder irre ich mich?

Bin sehr dankbar für jede Hilfe ...

Kampi

ein klarer fall fuern dijkstra wuerd ich meinen:

http://en.wikipedia.org/wiki/Dijkstra%27s_algorithm

[edit]
wenn es "spanning" sein soll, dann nimm kruskal ( http://en.wikipedia.org/wiki/Kruskal%27s_algorithm )
[/edit]

natural_born_ch

Das es den gibt, ist mir bewusst. Und doch weiß ich nicht wirklich, was du mir zu sagen versuchst ...

Kampi

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

Jetzt mitmachen!