Dijkstra-Algorithmus

[daniel-reinhold]

Hallo Leute,

ich habe derzeit ein totales Problem: Ich weiß einfach nichts mit dem Dajkstra- und Bellman-Ford Algorithmus anzufangen. Ich habe absolut keine Ahnung wie ich erklären soll, wie sie funktioniere, noch wie ich die Arbeitsweise der beiden Algorithmen auf Papier darstellen kann. Ich habe nun 4 Stunden damit verbracht, mich im Internet schlau zu machen, aber es kommt einfach nichts brauchbares zustande. Ich benötige dringend eure Hilfe.

[el_pollo_diablo]

Vielleicht helfen Dir ja auch die Erklärungen auf der Seite der Technischen Universität München: https://www-m9.ma.tum.de/graph-algorithms/spp-dijkstra/index_de.html

Dort kann man verschiedene Algorithmen Schritt für Schritt mit jeweiliger Erklärung durchlaufen und sieht die Vorgehensweise visuell.

Bearbeitet 10. Februar 2021 von el_pollo_diablo

[TooMuchCoffeeMan]

Ehrlich gesagt kann ich dein Problem gerade nicht ganz nachvollziehen. Ich finde die Erklärung zum Dijkstra Algorithmus auf Wikipedia eigentlich sehr eingängig und sie wird sogar anhand eines sehr verständlichen Beispiels mit mehreren Bildern erklärt. Wie genau können wir dir da jetzt in Textform helfen wenn dir die Erklärung auf Wikipedia schon nicht ausreicht? Was konkret ist dein Verständnisproblem? An welchem Schritt des Algorithmus hakt es? Und was willst du da groß zu Papier bringen? Den Pseudocode?

https://de.wikipedia.org/wiki/Dijkstra-Algorithmus

Bearbeitet 10. Februar 2021 von TooMuchCoffeeMan

[lessbess]

Da musst du schon genauer ausführen wo dein Verständnisproblem liegt. Gerade Graphenalgorithmen sind ja eigentlich sehr anschaulich, da gibt es hunderte Illustrationen zu.

[pr0gg3r]

Wenn wir von Anfang an beginnen: wir haben gegeben einen gewichteten(!) Graphen. Ein Graph besteht aus Kanten und Knoten. Bei einem gewichteten Graphen haben alle Kanten einen Wert (das Gewcht). Nun möchten wir von einem Knoten (zB "S" wie Start) zu einem beliebigen anderen Knoten (zB "Z" wie Ziel) gelangen. Aber nicht nur über einen zufälligen Weg, sondern den Weg mit den geringsten Gewicht.

Soweit verständlich? Das sind die Grundlagen, um die Aufgabenstellung zu verstehen (Formeln mal weggelassen, da man die erst mal nicht für das Verständnis braucht).

Nun gibt es verschiedene Möglichkeiten, den Pfad mi dem geringsten Gewicht (umgangssprachlich könnte man auch "den kürzesten Pfad" sagen) zu finden. Eine - aber nicht die einzige - Möglichkeit ist der Dijkstra-Algorithmus.

Dieser funktioniert so: du gehst von S zu jedem anderen anliegenden Knoten und merkst dir das Gewicht wie zB S->A 10, S->B 20, S->C 5, S->D 8. Nun nimmst du den Pfad mit dem geringsten Gewicht (hier S->C: mit dem Gewicht 5). Nun gehst du von C aus zu allen anderen anliegenden Knoten (zB C->E: 10, C->F: 50, C->G: 6) und addierst derren Gewicht zu dem Gewicht von S->C hinzu. Daraus folgt S->C->E: 15, S->C->F: 60, S->C->G: 11. Bevor du jetzt weiter gehst, suchst du von allen bisherigen gegangenen Wegen den mit dem geringsten Gewicht raus. Das heißt, nicht S->C-G mit 11 Kosten ist bisher der kürzeste, sondern S->A mit 10. Nun machst du das gleiche wie bei C mit A. Dann suchst du wieder von allen den kürzesten raus,  usw. bis du das Ziel erreicht hast.

Im Grunde ist es ganz einfach: du merkst dir immer die bisherigen Wege und suchst dann den kürzesten Weg (den Weg mit am wenigsten Gewicht) raus. Dann rechnest du von dem Kürzesten Weg wieder den Weg  zu den nächsten Knoten. Und nimmst dann wieder den kürzesten Weg usw. bis du beim Zielknoten angelangt bist.