Das Video kommt von YouTube: erst beim Abspielen verbindet sich die Seite mit YouTube (Google).
Der DIJKSTRA ALGORITHMUS (einfach erklärt) #Netzwerktechnik
Das Wichtigste aus dem Video
Tipp auf eine Zeit – das Video springt genau dorthin.
Transkriptautomatisch erstellt · 49 Zeilen
- in diesem video land zu wieder dijkstra algorithmus funktioniert und wo man ihn einsetzt
- [Musik] woher weiß ein paket welchen weg es durch ein netzwerk nehmen muss um von einem router es zu einem ziel gut dazu
- gelangen ganz einfach durch eine guten protokoll dass ein algorithmus nutzt mit dem man den kürzesten weg von einem bestimmten
- router zu einem anderen routen im netzwerk berechnen kann der algorithmus mit dem das möglich ist heißt dijkstra algorithmus des links
- date routing protokoll open shortest path first platz diesen algorithmus mit dem das wissen über die kosten zum erreichen von routern innerhalb des
- netzwerks aufgebaut werden kann als basis wird ein netzwerk betrachtet das aus verschiedenen knotenpunkten zum beispiel unten besteht die über links
- miteinander verbunden sind an diesen links sind kosten eingetragen damit ist der aufwand gemeint mit dem man von einem knoten oder runter zu
- einem anderen knoten und einem anderen bruder kommen kann diese quantifizierung nennt man auch metrik wenn es beim ringen um die anzahl
- der hawks geht das heißt wie viele router muss man durchlaufen bis man am ziel angekommen ist dann entsprechend die kosten an jedem gang einfach 1 an
- stelle des technischen begriffs router verwenden wir fortan im begriff knoten da der algorithmus auch in anderen bereichen routing angewendet wird als
- eingabe älter einen sogenannten gewichteten graf der unseren netzwerk darstellt und ein staat knoten es als ausgabe liefert der algorithmus die
- kürzesten wege von es zu allen anderen knoten im netzwerk wie läuft der algorithmus ab erstens die initialisierung hier wird zunächst eine
- liste mit allen untersuchten knoten erstellt dann werden die kosten zum erreichen des staates knotens auf null gesetzt logisch wenn wir beim start
- knoten anfangen dann brauchen wir null aufwand um zum start knoten zu kommen zudem wenn die kosten aller anderen knoten auf unendlich gesetzt zweitens
- setzte den knoten mit den geringsten kosten als aktuell besuchten knoten wenn es kein knoten mit geringsten kosten gibt zum beispiel bei zwei knoten mit
- denselben kosten erreicht werden können wähle zufällig einen von ihnen aus drittens berechnet von dem aktuell besuchten knoten aus schritt 2 die
- kosten zu seinen direkten nachbarn durch addition der eigene kosten zu den kosten entlang der kante bzw des weges zu dem entsprechenden nachbarn
- viertens wenn den schritt 3 entstandenen kosten geringer sind als die des aktuellen knoten zum erreichen des nachbarn
- denn er setzte diese durch die geringeren kosten und setzte den aktuell besuchten knoten als dessen vorgänger ansonsten mache einfach mit den nächsten
- schritt weiter fünfter wurden alle knoten besucht falls nein mache bei schritt 2 weiter falls ja ende der algorithmus so
- wir wollten diesen theoretisch betrachtet ein algorithmus jetzt natürlich auch mit leben füllen betrachten dazu das folgende netzwerk
- von dem router es aus sollen die kürzesten wege zu allen anderen routen berechnet werden das ergebnis wird in einer tabelle
- gespeichert für diese gibt es verschiedene darstellungsmöglichkeiten die du für gewöhnlich am anfang einer vorlesung gezeigt bekommst in unserer
- tabelle finden sich nun die einzelnen knoten nahmen die kosten zum erreichen dieses knotens und der direkte vorgänger habe denen dieser knoten erreicht wird
- wieder bei der initialisierung weisen wir den knoten es die kosten 0 und allen weiteren knoten die kosten unendlich zu zudem definieren wir eine liste mit
- einem bereits besuchten knoten die zu beginn natürlich leer ist wir beginnen nun bei dem start knoten es von dort aus können wir den knoten a und
- d erreichen die kosten von es sind 0 wir erreichen also indem wir 0 + 20 rechnen da 20 kleiner als unendlich ist setzen wir
- unendlich durch die neu berechneten kosten und legen es als den vorgänger von aaa fest wir erreichen de in dem wir von es aus 0 + 10 rechnen da 10 kleiner
- sohn endlich ist ersetzen wir unendlich durch die neu berechneten kosten und legen es als den vorgänger von b fest jetzt kommt es in die liste der bereits
- besuchten knoten wurden alle knoten besucht nein deshalb machen wir mit dem bislang um besuchte knoten weiter der die
- geringsten kosten hat das ist in diesem fall knoten de von dort aus erreichen wir die knoten as a und c da es bereits besucht wurde ignorieren wir diesen
- knoten erreichen wir von dem aus mit den kosten 10 + 20 also 30 30 nicht kleiner als 20 ist wird keine änderungen vorgenommen
- c erreichen wir von dem aus mit den kosten 10 + 50 also 60 da 60 kleiner als unendlich ist setzen wir unendlich durch die neu berechneten
- kosten und legen de als den vorgänger von c fest jetzt kommt denen die liste der knoten die bereits besucht wurden wurden alle knoten bereits besucht nein
- deshalb machen wir mit den bislang unbesiegten knoten weiter der die geringsten kosten hat das ist in diesem fall knoten aa- von aa aus erreichen wir
- die knoten sd s&d können wir ignorieren da diese bereits besucht wurden von aus erreichen wir den knoten 10 mit den kosten 20 bis
- 50 also 70 da 70 größer als 60 ist wird keine änderung vorgenommen der knoten b kann mit den kosten 20 20 also 40 erreicht werden
- dafür zu klein als man endlich ist ersetzen wir unendlich durch die neu berechneten kosten und legen als sein vorgänger von b fest jetzt kommt an die
- liste der knoten die bereits besucht wurden wurden nun alle knoten bereits besucht 9 deshalb machen wir den bislang
- unbesiegten knoten weiter die geringsten kosten hat das ist in diesem fall knoten b von b aus erreichen wie knoten a und c a konvertieren da dieser bereits besucht
- wurde von b aus erreichen wir den knoten 10 mit den kosten 40 plus 10 also 50 50 kleinert 60 ist setzen wir die kosten von c durch die neu
- berechneten kosten und legen es den vorgänger von c fest jetzt kommt gehen die liste der knoten die bereits besucht wurden
- nun ist noch ein knoten und besucht nämlich c von ihm aus erreichen wir nur bereits besuchte knoten und es kann auch keine weitere kostenreduktionen erfolgen
- dh der algorithmus terminiert an dieser stelle wenn du mit der ergebnistabelle nur den kürzesten weg von dem start knoten zu einem bestimmten entknoten
- berechnen willst du diesen rückwärts aus der tabelle ab wie funktioniert das nehmen wir andere möchte ist von knoten es zu knoten c du schaust zunächst in
- der ersten spalte der tabelle nach wo sich der knoten c befindet du liest dessen vorgänger das ist in diesem fall b ab und schreibt ihm vor
- dass c nun dies zu den vorgänger von b das ist ab und schreibt auch diesen vor dass b als letztes liest du noch den vorgänger von ab und er jetzt den staat
- knoten der kürzeste weg von a nach c führt also von es überall über b bis hin zu 10 vielen dank fürs zu sehen solltest du
- weitere fragen haben kannst du sie gerne unten in den kommentaren posten
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 …
DistanzvektoralgorithmusBeim Distanzvektoralgorithmus (auch bekannt als Distanzvektor-Routing oder Distance Vector Routing) handelt es sich um ein dynamisches Routing-Protokoll …
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 Floyd und WarshallDer Floyd-Warshall-Algorithmus basiert auf dem Prinzip der dynamischen Programmierung. ... Algorithmus von Dijkstra · Bellman-Ford-Algorithmus. Literatur.