Der DIJKSTRA ALGORITHMUS (einfach erklärt) #Netzwerktechnik
Florian Dalwigk
https://www.youtube.com/watch?v=KiOso3VE-vI

Transkript (automatisch erstellt)

0:00 in diesem video land zu wieder dijkstra algorithmus funktioniert und wo man ihn einsetzt
0:06 [Musik] woher weiß ein paket welchen weg es durch ein netzwerk nehmen muss um von einem router es zu einem ziel gut dazu
0:16 gelangen ganz einfach durch eine guten protokoll dass ein algorithmus nutzt mit dem man den kürzesten weg von einem bestimmten
0:22 router zu einem anderen routen im netzwerk berechnen kann der algorithmus mit dem das möglich ist heißt dijkstra algorithmus des links
0:30 date routing protokoll open shortest path first platz diesen algorithmus mit dem das wissen über die kosten zum erreichen von routern innerhalb des
0:37 netzwerks aufgebaut werden kann als basis wird ein netzwerk betrachtet das aus verschiedenen knotenpunkten zum beispiel unten besteht die über links
0:44 miteinander verbunden sind an diesen links sind kosten eingetragen damit ist der aufwand gemeint mit dem man von einem knoten oder runter zu
0:52 einem anderen knoten und einem anderen bruder kommen kann diese quantifizierung nennt man auch metrik wenn es beim ringen um die anzahl
0:59 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
1:06 stelle des technischen begriffs router verwenden wir fortan im begriff knoten da der algorithmus auch in anderen bereichen routing angewendet wird als
1:14 eingabe älter einen sogenannten gewichteten graf der unseren netzwerk darstellt und ein staat knoten es als ausgabe liefert der algorithmus die
1:22 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
1:31 liste mit allen untersuchten knoten erstellt dann werden die kosten zum erreichen des staates knotens auf null gesetzt logisch wenn wir beim start
1:38 knoten anfangen dann brauchen wir null aufwand um zum start knoten zu kommen zudem wenn die kosten aller anderen knoten auf unendlich gesetzt zweitens
1:47 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
1:55 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
2:02 kosten zu seinen direkten nachbarn durch addition der eigene kosten zu den kosten entlang der kante bzw des weges zu dem entsprechenden nachbarn
2:10 viertens wenn den schritt 3 entstandenen kosten geringer sind als die des aktuellen knoten zum erreichen des nachbarn
2:16 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
2:24 schritt weiter fünfter wurden alle knoten besucht falls nein mache bei schritt 2 weiter falls ja ende der algorithmus so
2:33 wir wollten diesen theoretisch betrachtet ein algorithmus jetzt natürlich auch mit leben füllen betrachten dazu das folgende netzwerk
2:38 von dem router es aus sollen die kürzesten wege zu allen anderen routen berechnet werden das ergebnis wird in einer tabelle
2:45 gespeichert für diese gibt es verschiedene darstellungsmöglichkeiten die du für gewöhnlich am anfang einer vorlesung gezeigt bekommst in unserer
2:52 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
2:59 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
3:08 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
3:16 d erreichen die kosten von es sind 0 wir erreichen also indem wir 0 + 20 rechnen da 20 kleiner als unendlich ist setzen wir
3:26 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
3:35 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
3:43 besuchten knoten wurden alle knoten besucht nein deshalb machen wir mit dem bislang um besuchte knoten weiter der die
3:50 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
4:00 knoten erreichen wir von dem aus mit den kosten 10 + 20 also 30 30 nicht kleiner als 20 ist wird keine änderungen vorgenommen
4:09 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
4:17 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
4:27 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
4:35 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
4:45 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
4:55 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
5:03 liste der knoten die bereits besucht wurden wurden nun alle knoten bereits besucht 9 deshalb machen wir den bislang
5:09 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
5:19 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
5:29 berechneten kosten und legen es den vorgänger von c fest jetzt kommt gehen die liste der knoten die bereits besucht wurden
5:36 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
5:44 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
5:52 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
6:01 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
6:08 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
6:17 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
6:26 weitere fragen haben kannst du sie gerne unten in den kommentaren posten