QG-ITG

Das alte QG-Wiki

Benutzer-Werkzeuge

Webseiten-Werkzeuge


kurs:kursstufe:dijkstra:start

Dijkstra Algorithmus

Der Algorithmus von Dijkstra (nach seinem Erfinder Edsger W. Dijkstra) ist ein Algorithmus aus der Klasse der Greedy-Algorithmen und löst das Problem der kürzesten Pfade für einen gegebenen Startknoten. Er berechnet somit einen kürzesten Pfad zwischen dem gegebenen Startknoten und einem der (oder allen) übrigen Knoten in einem kantengewichteten Graphen.

Routenplaner sind ein prominentes Beispiel, bei dem dieser Algorithmus eingesetzt werden kann. Der Graph repräsentiert hier das Straßennetz, das verschiedene Punkte miteinander verbindet. Gesucht ist die kürzeste Route zwischen zwei Punkten.

Einige topologische Indizes, etwa der J-Index von Balaban, benötigen gewichtete Distanzen zwischen den Atomen eines Moleküls. Die Gewichtung ist in diesen Fällen die Bindungsordnung.

Dijkstras Algorithmus wird auch im Internet als Routing-Algorithmus im OSPF- und OLSR-Protokoll eingesetzt. Das letztere Optimized Link State Routing-Protokoll ist eine an die Anforderungen eines mobilen drahtlosen LANs angepasste Version des Link State Routing. Es ist wichtig für mobile Ad-hoc-Netze. Eine mögliche Anwendung davon sind die freien Funknetze.

Auch bei der Lösung des Münzproblems, eines zahlentheoretischen Problems, das auf den ersten Blick nichts mit Graphen zu tun hat, kann der Dijkstra-Algorithmus eingesetzt werden.

— Wikipedia, https://de.wikipedia.org/wiki/Dijkstra-Algorithmus (18.04.2016)

Arbeitsauftrag

  • Lade die zip Datei herunter, das Passwort gibts im Unterricht!
  • Bearbeitet den Text in Zweiergruppen, auch die Übungen und Aufgaben! Drucke dazu die Karten aus!
kurs/kursstufe/dijkstra/start.txt · Zuletzt geändert: 18.04.2016 10:42 von sbel