Dijkstra Algorithmus - Beispiel mit Graph und Tabelle veranschaulicht!
Studyflix
https://www.youtube.com/watch?v=8NsD01kzJwg

Transkript (automatisch erstellt)

0:00 du verstehst einfach nicht den ablauf des dijkstra algorithmus kein problem wir schauen uns schritt für schritt an du willst ganz viele kostenlose videos
0:10 zu bwl und vwl dann kommen auf study flex de der dijkstra algorithmus ist ein sogenannter greedy algorithmus
0:19 er hilft dir die kürzesten bzw kostengünstigsten wege zu berechnen die kanten gewichte so nennt man die kosten um von einem punkt zum nächsten
0:28 zu kommen dürfen beim dijkstra algorithmus nicht negativ sein falls jedoch negative kosten auftreten solltest du besser den bällen ford
0:36 algorithmus anwenden um den dijkstra algorithmus zu verstehen schauen wir uns am besten ein konkretes beispiel an stell dir vor du planst deine nächste
0:47 reise die frage ist wie du deine möglichen reiseziele am günstigsten erreichen kannst wie kommst du zum beispiel am schnellsten von nürnberg
0:55 nach kopenhagen in dem du über hamburg oder über berlin fest schauen wir uns doch einen grafen einmal genauer an die strecke hat den kanten
1:06 gewicht von 100 das heißt du gelangt zu diesen kosten von ort a nach b das wäre geklärt dann können wir jetzt damit starten das beispiel per hand
1:15 durchzurechnen natürlich kannst du es auch in java implementieren zuerst muss du den algorithmus initialisieren
1:24 am besten legst du eine tabelle an um den überblick zu behalten in der ersten spalte trägst du die jeweilige iteration einen der du dich
1:32 befindest für jeden knoten gibst du dann die jeweiligen kosten und den direkten vorgänger an in der letzten spalte kannst du deinen
1:40 vorgehen verwalten das hilft ihr dabei einen guten überblick zu haben die kosten zum start knoten betragen 0 du bist ja schon zuhause zu deinen
1:51 möglichen reise orten ist noch kein weg bekannt darum bewertest du die kosten erst einmal mit unendlich das bleibt natürlich nicht so nach und nach werden
2:00 diese kosten verbessert jetzt benötigst du eine warteschlange in diese werden alle knoten die du bereits gefunden hast eingefügt da du bisher nur
2:10 deinen staat knoten kennst willst du diesen als erstes in eine warteschlange ein kommen wir zur ersten generation da in
2:18 der warteschlange nur ein element ist wirst du dieses aus und betrachtet die direkten nachfolger vom staat knoten aus können die knoten b und d erreicht
2:27 werden die kosten um vom staat knoten nach b zu kommen betragen 100 als vorgänger von knoten b trägst du den staat knoten in deine tabelle 1
2:37 genauso gehst du mit knoten de vor die kosten um vom staat knoten nach b zu kommen betragen 50 und als vorgänger trägst du ebenfalls den ersten knoten 1
2:48 die nachfolger des staates knotens hast du nun betrachtet du kannst ihn als erledigt markieren die beiden nachfolger knoten nimmst du an deine warteschlange
2:58 auf war das mit operation zwei nun willst du den knoten den du mit den geringsten kosten
3:05 erreicht aus deiner warteschlange aus das ist hier knoten betrachte jetzt die nachfolger die kosten von knoten b verändern sich nicht
3:16 der direkte weg vom staat knoten aus ist günstiger als der umweg über knoten de die neuen kosten von knoten ehe betragen jetzt 300 trage auch hier den direkten
3:27 vorgänger ein ergänzend eine warteschlange um den knoten knoten b ist ja bereits in der warteschlange knoten dem musst du von
3:38 jetzt an nicht weiter betrachten und kannst ihn als erledigt markieren nach diesem schema gehst du auch in der nächsten generation vor die kosten um
3:48 knoten zu erreichen betragen 200 und der vorgänger ist b bei knoten e verändert sich nichts update auch hier deine warteschlange in
3:58 dem du knoten b als erledigt markiert und c in die warteschlange aufnimmst in wir werden die nachfolger von knoten c
4:08 betrachtet das ist nur noch knoten doch du kannst erkennen dass du knoten ehe günstiger erreicht wenn du den weg über b und c wählst das heißt du erhältst
4:18 neue kosten von 250 und c als neuen vorgänger auch knoten kannst du nun als erledigt markieren
4:28 sehr gut du hast alle knoten abgearbeitet somit kannst du keinen weiteren knoten in die warteschlange aufnehmen
4:35 sie ist also leer das führt zum abbruch des algorithmus das war jetzt ganz schön viel wir haben es auch gleich geschafft
4:48 schauen wir uns nur noch kurz an was dir diese tabelle nun eigentlich sagt das ablesen aus der tabelle erfolgte kursiv nehmen wir uns zum beispiel knoten
4:59 genauer vor knoten e wird mit gesamtkosten von 250 erreicht der vorgänger ist knoten c diesen erreichst du am besten über b und
5:09 dorthin kommst du direkt vom staat knoten aus der kürzeste weg vom staat knoten zu ehe führt also über die knoten b und c
5:21 top die nächsten semesterferien können kommen denn genau so kannst du jetzt auch herausfinden wie du am besten von nürnberg nach kopenhagen kommst du hast
5:31 das thema verstanden teile es jetzt mit deinen freunden dann du weißt ja er hat das video gefallen noch mehr kostenlose videos gibt's auf study flex
5:43 de