Hallo,
wofür ist es gut einen minimalen Spannbaum eines Graphen zu bestimmen ?
Grüße,
Tris
Hallo,
um z.B. die minimalen Wege zwischen zwei Knoten zu bestimmen. Hat durchaus Praxisbezug für logistische Probleme.
Gruss
Enno
Hallo,
trotzdem würde ein minimaler Spannbaum aber nicht das „single source shortest path“ Problem lösen, oder ? Ich meine ein Pfad im minimalen Spannbaum muss nicht der kürzeste Weg zwischen zwei Knoten sein, oder ?
MfG,
Tris
[Bei dieser Antwort wurde das Vollzitat nachträglich automatisiert entfernt]
Hallo,
ja das ist richtig. Wenn man sich auf bestimmte Routen festlegt (besseres Bsp. wären wohl Schienenfahrzeuge), ist die Summe aller Verbindungen/Wege zwischen zwei Orten/Knoten minimal oder anders formuliert die durchschnittliche Entfernung zwischen zwei Orten wird minimiert. Für Einzelfälle, gibt es durchaus „Abkürzungen“.
Gruss
Enno