Das Video kommt von YouTube: erst beim Abspielen verbindet sich die Seite mit YouTube (Google).
Dijkstra Algorithmus - Beispiel mit Graph und Tabelle veranschaulicht!
Das Wichtigste aus dem Video
Tipp auf eine Zeit – das Video springt genau dorthin.
Transkriptautomatisch erstellt · 36 Zeilen
- 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
- zu bwl und vwl dann kommen auf study flex de der dijkstra algorithmus ist ein sogenannter greedy algorithmus
- 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
- zu kommen dürfen beim dijkstra algorithmus nicht negativ sein falls jedoch negative kosten auftreten solltest du besser den bällen ford
- 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
- 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
- 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
- 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
- durchzurechnen natürlich kannst du es auch in java implementieren zuerst muss du den algorithmus initialisieren
- 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
- befindest für jeden knoten gibst du dann die jeweiligen kosten und den direkten vorgänger an in der letzten spalte kannst du deinen
- 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
- 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
- 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
- deinen staat knoten kennst willst du diesen als erstes in eine warteschlange ein kommen wir zur ersten generation da in
- 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
- 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
- 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
- die nachfolger des staates knotens hast du nun betrachtet du kannst ihn als erledigt markieren die beiden nachfolger knoten nimmst du an deine warteschlange
- auf war das mit operation zwei nun willst du den knoten den du mit den geringsten kosten
- erreicht aus deiner warteschlange aus das ist hier knoten betrachte jetzt die nachfolger die kosten von knoten b verändern sich nicht
- 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
- vorgänger ein ergänzend eine warteschlange um den knoten knoten b ist ja bereits in der warteschlange knoten dem musst du von
- 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
- knoten zu erreichen betragen 200 und der vorgänger ist b bei knoten e verändert sich nichts update auch hier deine warteschlange in
- dem du knoten b als erledigt markiert und c in die warteschlange aufnimmst in wir werden die nachfolger von knoten c
- 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
- neue kosten von 250 und c als neuen vorgänger auch knoten kannst du nun als erledigt markieren
- sehr gut du hast alle knoten abgearbeitet somit kannst du keinen weiteren knoten in die warteschlange aufnehmen
- sie ist also leer das führt zum abbruch des algorithmus das war jetzt ganz schön viel wir haben es auch gleich geschafft
- 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
- genauer vor knoten e wird mit gesamtkosten von 250 erreicht der vorgänger ist knoten c diesen erreichst du am besten über b und
- 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
- 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
- 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
- de
Zum Nachlesen
Dijkstra-AlgorithmusDer Algorithmus von Dijkstra (nach seinem Erfinder Edsger W. Dijkstra) ist ein Algorithmus aus der Klasse der Greedy-Algorithmen und löst das Problem der …
Algorithmus von Floyd und WarshallDer Floyd-Warshall-Algorithmus basiert auf dem Prinzip der dynamischen Programmierung. ... Algorithmus von Dijkstra · Bellman-Ford-Algorithmus. Literatur.
Kürzester PfadFür nichtnegative Gewichtsfunktionen lassen sich der Dijkstra-Algorithmus bzw. der A*-Algorithmus anpassen, um die kürzesten Wege zu allen Knoten des Graphs …
Algorithmus von PrimDer Algorithmus von Prim dient der Berechnung eines minimalen Spannbaumes in einem zusammenhängenden, ungerichteten, kantengewichteten Graphen.