Quelle: dotnetpro
dojoLösung: graphen als Datenstruktur 16.11.2020, 00:00 Uhr

Kürzeste Wege finden

Algorithmen und Datenstrukturen sind zentrale Themen der Informatik. Mir ging es um Graphen als Datenstruktur und einen sehr wichtigen darauf basierenden Algorithmus.
Das ganze Leben ist ein Graph.“ – das waren die Worte meines Professors in der Vorlesung zur Graphentheorie. Ganz so einfach ist das Leben dann doch nicht, aber viele Probleme lassen sich tatsächlich mithilfe von Graphenalgorithmen lösen. So auch das Problem des kürzesten Weges. In einem Graphen mit gerichteten und gewichteten Kanten soll der kürzeste Weg zwischen zwei Knoten gefunden werden. Die Gewichtung der Kanten könnte beispielsweise die Entfernung zwischen zwei Orten sein oder auch die Fahrzeit. Gesucht ist dann der Weg mit der kürzesten Strecke oder der geringsten Fahrzeit. Der ­Dijkstra-Algorithmus [1] bietet hierfür ­eine Lösung.
Bild 1 zeigt ein Beispiel eines Graphen. In diesem Graphen gibt es einen Weg von Knoten 0 zu Knoten 5. Es existieren sogar zwei unterschiedliche Wege. Der eine führt von 0 über 1, 2 und 4 nach 5. Der andere führt von 0 über 1 direkt nach 5. Die wenigsten Knoten besucht der zweite Weg. Berücksichtigt man jedoch die Kantengewichte, ist der erste Weg der kürzere.

dotnetpro

Sie wollen zukünftig auch von den Vorteilen eines plus-Abos profitieren? Werden Sie jetzt dotnetpro-plus-Kunde
  • 2 Monate Gratis testen
  • Über 4.000 qualifizierte Fachartikel
  • Auf jedem Gerät verfügbar