Kann mir jemand einen konkreten Beispiel nennen, für wo man den shortest-Path und minimal spanning tree anwenden könnte?

1 Antwort

Ein Beispiel für die Anwendung von Dijikstra wäre, wenn wir schon beim Internet sind, die Wegsuche vom Router zum Zielrechner. Man will den Weg ja möglichst gering halten, um Zeit zu sparen, muss bei Ausfällen unter Umständen aber auch einen alternativen Pfad berechnen.

Woher ich das weiß:Studium / Ausbildung – Informatikstudent

callmemangothk 
Beitragsersteller
 03.06.2024, 17:44

Danke Seliba für dein Einsatz den ich sehr schätze! Wie wäre es aber z.b. im Bahnverkehr? Wie könnte im Bahnverkehr shortest path und minimal spanning tree hilfreich sein?

0
Seliba  03.06.2024, 17:49
@callmemangothk

Beim Bahnverkehr könnte man Dijikstra benutzen, wenn man beispielsweise Bahnhöfe als Knoten und die Verbindungen zwischen ihnen als Kanten auffasst, die mit der Zeit gewichtet sind. So könnte man den kürzesten Weg zwischen zwei Bahnhöfen berechnen, auch wenn eine Strecke kurzfristig ausfällt.

Beim MST könnte man vielleicht ein komplexes Streckennetz auf die effizientesten Verbindungen reduzieren, mit denen man trotzdem alle Stationen erreicht. Würde mir zumindest spontan so einfallen. Ob das in der Praxis sinnvoll wäre, ist eine andere Frage - es würde vermutlich dazu führen, dass manche Strecken deutlich stärker frequentiert und dadurch dauerhaft überlastet wären.

0