++**Kürzeste Wege**++ === ## Wie komme ich am schnellsten von einem Ort zum anderen? --- ### ++1. Problem:++ #### Gegeben: - ein Stadtplan - Startpunkt(M) - Zielpunkt(F) #### Frage: - Wie finde ich den kürzesten Weg von M zu F? --- ### ++2. Lösungsvorbereitung:++ 1. Stadtplan ausbreiten 2. Bindfäden entlang der Straßen legen 3. Fäden an Kreuzungen und Abzweigungen verknoten (auch bei (möglichen) Start- und Zielpunkten) 4. Knoten eindeutig markieren --- #### Ergebnis:  --- ### ++3. Lösungsfindung:++ :mag_right: 1. Bindfäden-Gespinst am Startpunkt fassen 2. Knoten langsam nach oben ziehen - Knoten für Knoten löst sich - wenn Zielpunkt in der Luft, stoppen 3. Zielpunkt ausfindig machen 4. Straff gespannte Fäden zurückgehen - eindeutiges Finden des Startpunktes - Folge von Knoten ist kürzester Weg 5. Entfernung mit Maßband an straffem Weg messen --- ###### Abbildung zeigt Lösungsfindung:  --- ### ++4. Bewertung:++ #### Warum ist der gefundene Weg der Kürzeste? - Start und Ziel hätten sich sonst nie so weit voneinander entfernt --- #### ++Nachteile dieser Lösung:++ - aufwendig - unpräzise - automatisierbar ### => Der Computer sollte diese Aufgabe übernehmen! :computer: --- ## ++Der Dijkstra-Algorithmus++ (1956) --- ### ++1. Allgemeine Beschreibung:++ | Eingabe :arrow_down: | Ausgabe :arrow_up: | | -------- | -------- | | - virtuelles Netz mit:| - Länge des kürzesten Wegs vom Startknoten aus zu jedem Knoten | | ↳ Fäden mit Längenangaben | | ↳ Knoten | -Teilmenge Fäden zum Rückverfolgen der kürzesten Wege | --- ### ++2. Pseudocode:++ Der hier angegebene Pseudocode berechnet nun die Entfernungen aller erreichbarer Knoten vom Startknoten: ```javascript 1 function kürzesteWege (X) 2 alle Knoten liegen, alle d[](*) unendlich, nur d[Startknoten]=0 3 while es liegende Knoten gibt do 4 v := der liegende Knoten mit kleinstem d[v] mache v hängend 5 for all Fäden von v zu einem Nachbarn u der Länge L do 6 if d[v]+L < d[u] then d[u] = d[v]+L {kürzerer Weg hin zu u gefunden, führt über v} 7 endfor 8 endwhile 9 end ``` ###### *d[] = Baum mit allen Knoten und deren Entfernungen --- ### ++3. Erläuterung:++  - Nach 10 Schritten des Algorithmus - Knoten F ist erreicht --- ### ++4. Zusammenfassung:++ #### Problem: - Finde den kürzesten Weg vom Start- zum Zielpunkt in einem gegebenen Straßennetz #### Lösung: - Der Algorithmus von Dijkstra berechnet die kürzesten Wege von einem Startpunkt zu allen erreichbaren Zielpunkten - arbeitet analog zur trickreichen Lösung mittels Bindfäden --- >"If you want more effective programmers, you will discover that they should not waste their time debugging, they should not introduce the bugs to start with." ~ Edsger Wybe Dijkstra (1930-2003) ##### Created by Vincent Lohmann, Muhammed Konaç & Dominik Stachel --- # Vielen Dank für eure Aufmerksamkeit! --- ### Feedbackvorschläge: --- >"Eine mega coole Präsentation, der jeder mal hätte beiwohnen müssen" >~_Der Spiegel_ aka. Dominik >"Der Vortrag war phänomenal" >~_Die Welt_ aka. Vincent >"Für unseren Geschmack zu wenig Frauen!" >~_Der Playboy_ aka. Muhammed