Zum Inhalt springen
  • 0

Dijkstra-Algorithmus


 Teilen

Frage

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.

Link zu diesem Kommentar
Auf anderen Seiten teilen

4 Antworten auf diese Frage

Empfohlene Beiträge

  • 1

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 von el_pollo_diablo
Link zu diesem Kommentar
Auf anderen Seiten teilen

  • 0

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 von TooMuchCoffeeMan
Link zu diesem Kommentar
Auf anderen Seiten teilen

  • 0

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.

Link zu diesem Kommentar
Auf anderen Seiten teilen

Deine Meinung

Schreibe jetzt und erstelle anschließend ein Benutzerkonto. Wenn Du ein Benutzerkonto hast, melde Dich bitte an, um unter Deinem Benutzernamen zu schreiben.

Gast
Diese Frage beantworten...

×   Du hast formatierten Text eingefügt.   Formatierung wiederherstellen

  Nur 75 Emojis sind erlaubt.

×   Dein Link wurde automatisch eingebettet.   Einbetten rückgängig machen und als Link darstellen

×   Dein vorheriger Inhalt wurde wiederhergestellt.   Editor leeren

×   Du kannst Bilder nicht direkt einfügen. Lade Bilder hoch oder lade sie von einer URL.

 Teilen

Fachinformatiker.de, 2021 by SE Internet Services

fidelogo_small.png

Schicke uns eine Nachricht!

Fachinformatiker.de ist die größte IT-Community
rund um Ausbildung, Job, Weiterbildung für IT-Fachkräfte.

Fachinformatiker.de App

Download on the App Store
Get it on Google Play

Kontakt

Hier werben?
Oder sende eine E-Mail an

Social media u. feeds

Jobboard für Fachinformatiker und IT-Fachkräfte

×
×
  • Neu erstellen...

Wichtige Information

Fachinformatiker.de verwendet Cookies. Mehr dazu in unserer Datenschutzerklärung