LOGIN | NEU REGISTRIEREN

Schule > Mathematik > Algebra und Funktionen > Bestimmung des kürzesten Weges mit Hilfe des Dijkstra-Algorithmus

Bestimmung des kürzesten Weges mit Hilfe des

Dijkstra-Algorithmus
Esther Albrecht
Mathe Lk Herr Seyfert
20.06.2004

Inhalt:
Vorwort........................................3
Einleitung....................................4
Modellbildung..............................5
Der Dijkstra-Algorithmus.............9
Dijkstra-Algorithmus allgemein..17
Quellen......................................19
Eigenständigkeitserklärung........20
Vorwort
In meiner Facharbeit beschäftige ich mich mit dem Problem des kürzesten Weges.
Hierbei wähle ich den Dijkstra-Algorithmus, der zur Suche eines kürzesten Weges zwischen einem Start- und einem Zielpunkt dient.
Ich betrachte zwei konkrete Problemstellungen und verallgemeinere sie zu einer Modell-Problemstellung, die ich mit Hilfe des Dijkstra-Algorithmus löse.
Ich stütze mich in dieser Facharbeit überwiegend auf das Buch „Das Geheimnis des kürzesten Weges“ von Peter Gritzmann und René Brandenberg, wobei ich unter anderem auch das Internet einbeziehe.
Einleitung (Problem des kürzesten Weges)
Wir gehen von einen Startpunkt S und einen Zielpunkt Z aus.Um diese beiden Punkte zu erreichen, benötigt man einen Weg über viele andere Punkte.
Das Problem bei der ganzen Sache ist allerdings, dass zwar alle Wege bekanntlich nach Rom führen, wir aber meistens den schnellsten Weg suchen.
Nehmen wir eimal an, wir wollen von Dormagen nach Wien fahren.Dann ist S Dormagen und Z Wien.Da die Strecke sehr lang ist, möchten wir sie mit minimaler Fahrtzeit erreichen.Wir wählen daher die Autobahn.

Hierbei ist allerdings zu beachten, dass es eine Vielzahl von Autobahnen, die man bei dieser Fahrt nutzen kann, gibt und man bei jedem Autobahnkreuz die gewählte Autobahn wechseln kann, was zu sehr vielen möglichen Wegen führt:
einer kombinatorischen Explosion.
Da bei vielen Wegen auch die Möglichkeit besteht, dass es mehrere gleich lange Wege gibt, suchen wir auch nicht den kürzesten Weg, sondern einen kürzesten Weg, denn es könnte mehrere Wege geben, die eine minimale Fahrzeit verursachen.Wir benötigen aber nur eine optimale Strecke.
Die Lösung des Problems liefert der Dijkstra-Algorithmus.

Modellbildung
Als weiteres Beispiel wähle ich den U-Bahn-Fahrplan von Wien in vereinfachter Form.Vereinfacht bedeutet, dass hier nur noch die Stationen, an denen man umsteigen kann, eingezeichnet sind und nicht mehr alle Haltestellen.
Die Kreise symbolisieren die Haltestellen;sie sind jeweils mit ihrem Anfangsbuchstaben gekennzeichnet.
Die farbigen Linien stehen für die jeweiligen U-Bahn-Linien.
Die Zahlen an den Linien geben die Anzahl der Teilstrecken zwischen den jeweiligen Haltestellen an.
Nehmen wir also einmal zur Verdeutlichung an, wir fahren vom Westbahnhof W zum Volkstheater V mit der gelben U-Bahn-Linie (also der U3).
Dann sehen wir im Beispiel, dass an der Strecke die Zahl 3 steht.
Die 3 bedeutet, dass es zwei Haltestellen zwischen dem Westbahnhof und dem Volkstheater gibt, nämlich Zieglergasse und Neubaugasse.Wir müssen also vom Westbahnhof aus drei Teilstrecken fahren, nämlich vom Westbahnhof zur Zieglergasse, von der Zieglergasse zur Neubaugasse und von der Neubaugasse zum Volkstheater.
Vergleichen wir nun dieses Beispiel mit der Autobahnstrecke Dormagen-Wien.
Bei beiden Beispielen haben wir Gemeinsamkeiten, die wir in eine allgemeingültige Vorstellung übertragen können.
In beiden Fällen haben wir einen Start- und Zielpunkt.
Bei der Autobahn haben wir Abfahrten und Autobahnkreuze; bei der U-Bahn Haltestellen und Umsteigemöglichkeiten, in beiden Fällen haben wir Knotenpunkte: Autobahnkreuze bzw. Haltestellen mit Umsteigemöglichkeit
Diese Autobahnkreuze und Umsteigemöglichkeiten nennt man auch im Modell kurz Knoten.
Die Verbindungen zwischen Knoten nennt man Kanten bzw. Bögen. Kanten sind die allgemeinen Verbindungen zwischen Knoten; Bögen sind gerichtet,d.h. dass sie nicht wie die Kanten in beide Richtungen genutzt werden können sondern nur in eine.Die Richtung der Bögen gibt ein Pfeil an.
Eine Kante kann durch zwei Bögen in beide Richtungen ersetzt werden.
Ein Bogen kann im Beispiel z.B. eine Autobahnvollsperrung in eine Richtung symbolisieren.
Knoten
Bogen
Kante
Es gibt allerdings noch andere Faktoren.
Bei der Autobahnstrecke Dormagen-Wien ist das die Zeit, denn gesucht ist die kürzeste Fahrtzeit; bei der U-Bahn ist dieser Faktor die Strecke, wobei dies nur als Beispiel gedacht ist.
Diese Gewichtung der einzelnen Strecken, also der Kanten und Bögen, nennt man Kanten- und Bogengewichte; Kantengewichte sind die Gewichte, die bei Kanten auftreten, Bogengewichte die Gewichte der Bögen.
Bogengewicht

Kantengewicht
Bei einer solchen Modellbildung werden in der Regel auch Vereinfachungen vorgenommen, z.B. spielt der Wochentag meist keine Rolle.
Die Gewichte in dem entstandenen Graphen sind immer positiv, da sie Fahrzeiten, Strecken oder ähnliches repräsentieren.

Der Graph bei unserem Wiener U-Bahn-Plan war schon etwas verändert dargestellt.Wenn die Haltestellen annährend ihrer geographischen Lage entsprechen sollten, dann sähe der Graph etwa so aus:
Für den Graphen ist es absolut unerheblich ob die Knoten entsprechend ihrer geographischen Lage angeordnet wurden, entscheidend ist nur die Beziehung zwischen den Knoten über die Kanten und Bögen und deren Gewichtung.

Der Dijkstra-Algorithmus
E.W.Dijkstra hat ein systematisches Verfahren (also einen Algorithmus) zur Lösung des Problems des kürzesten Weges entwickelt.
Seine Idee war es, schrittweise vorzugehen, da man nicht von vorneherein von einem kürzesten Weg von S nach Z ausgehen kann, d.h. man bestimmt in jedem Schritt einen Knoten K, für den man einen kürzesten Weg von S nach K kennt.
Da es endlich viele Knoten gibt und in jedem Schritt ein weiterer Knoten mit einem bekannten kürzesten Weg zu diesem Knoten gefunden wird, ist nach endlich vielen Schritten der Zielknoten ein solcher Knoten K mit einem kürzesten Weg, womit wir unser Ziel erreicht haben.
Der Ansatz ist ähnlich der der vollständigen Induktion.

Hierzu ein Beispielgraph:
Wir haben nun also einen Startpunkt S.
Der kürzeste Weg vom Startpunkt aus ist der Startpunkt selbst.
Zur Veranschaulichung färben wir ihn rot ein.
Rot-markierte Knoten bedeuten, dass wir zu ihnen einen kürzesten Weg gefunden haben.
Nun suchen wir alle Wege (Kanten und Bögen), die von S zu einem anderen Knoten führen und färben sie grün ein.
Grüne Kanten und Bögen sind also potenzielle kürzeste Wege.
Wir haben im Beispiel also zwei mögliche kürzeste Wege gefunden, von denen wir im nächsten Schritt einen als real kürzesten Weg auswählen werden.
Dazu beziehen wir die Bogengewichte ein.
Die beiden grünen Bögen führen zu den Knoten A und B.
Der Bogen, der zu A führt hat die Abstandsmarke 2, d.h. dass der Weg vom Knoten S bis A das Gewicht 2 hat. Um dies zu verdeutlichen, schreiben wir dies direkt in den Knoten A. Das tun wir analog auch bei Knoten B.
Als nächstes sieht man sich alle noch nicht passierten -also nicht rot-gefärbten- Knoten an.Der Knoten mit der geringsten Abstandsmarke (der kleinsten Zahl) ist der Knoten mit dem geringsten Abstand zu S (der Weg zwischen diesem Knoten und S ist also bis jetzt der kürzeste Weg zwischen ein oder mehreren Knoten und S) :Der Knoten wird rot gefärbt; der benutzte Bogen wird (als kürzester Weg) dunkelrot markiert.
Wir haben jetzt also einen kürzesten Weg nach A, was bedeutet, dass wir keinen anderen kürzesten Weg mehr nach A benötigen.Somit wird der Bogen von C nach A nutzlos; wir löschen ihn deswegen. Analog löschen wir auch den Bogen von B nach A.

Der gesamte Vorgang wiederholt sich von nun an solange, bis S mit dem Zielknoten Z verbunden ist, wobei jedoch einige Kleinigkeiten hinzukommen:
Wir färben die Kanten und Bögen, die von den bisher bekannten kürzesten Wegen,also von S und A ausgehen, grün.
Die Kanten und Bögen führen nun zu B und D.
Von A aus wird jedes Gewicht +2 gerechnet; also addieren wir zu dem Wert, der in dem Knoten steht, von dem wir ausgehen, die Zahl 2.(Bei S war dieser Wert 0, weshalb wir nichts addieren mussten.)
Daraus folgen die Werte für C und D.
Bei dem Knoten B gibt es noch eine Besonderheit, da es zu B zwei mögliche Wege gibt. Da wir den kürzesten Weg suchen, nehmen wir den kürzesten potenziellen Wert, also lassen wir den Bogen von S nach B weg, da wir schon einen kürzeren Weg zu B kennen, nämlich den Weg über A.
Unsere möglichen kürzesten Wege gehen jetzt nur noch von A aus.
Wir nehmen als neuen kürzesten Weg wieder den Knoten mit der geringsten Abstandsmarke also B.
Wir suchen wieder alle potenziellen kürzesten Wege.
Jetzt sehen wir, dass es einen kürzeren Weg nach D gibt als über die Kante von A aus, weswegen wir sie nicht mehr benötigen.
Wir haben jetzt zwei Möglichkeiten für den möglichen kürzesten Weg und entscheiden uns für den Bogen von B nach D, da die Abstandsmarke von D am geringsten ist.
Der Bogen von C nach D ist irrelevant geworden und kann gelöscht werden.
Neue potenziell kürzeste Wege sind die Bögen von C nach D und der Bogen von D zu Z.
Der Knoten C ist über A schneller zu erreichen als über D, weshalb der Bogen von D nach C gelöscht wird.
Die kürzeste Strecke führt über C, denn C hat die geringste Abstandsmarke.
Es gibt jetzt nur noch zwei Wege nach Z, nämlich über C und über D.
Der Weg über D ist länger als über C, weshalb man den Weg über B und D löschen kann, denn er hat sich als Sackgasse herausgestellellt.
Wir müssen jetzt also nur noch C mit Z verbinden und haben somit unseren kürzesten Weg von S nach Z.
Den kürzesten Weg von S nach Z stelle ich noch einmal vereinfacht dar, in dem ich die Bögen grade skizziere .
Der kürzeste Weg ist dank Dijkstra-Algorithmus gefunden.
Dijkstra-Algorithmus allgemein

Allgemein bedeutet dies:
Die Knoten, für die man bereits einen kürzesten Weg kennt, markiert man rot und schreibt die bekannte Minimaldistanz zum Startknoten S in den Knoten.
-Im Startschritt markiert man den Startknoten S rot (immer kürzester Weg mit
Länge 0)

-In jedem einelnen Schritt geht man volgendermaßen vor:
*man betrachtet alle Knoten, die man vom zuletzt rot markierten Knoten R
erreicht (im Beispiel Knoten, zu denen grün gefärbte Kanten und Bögen
führen).
K ist einer dieser Knoten, den man von einem rot markierten Knoten R
erreicht.Man berechnet nun die Distanz d von S nach K über R.

Es ergeben sich zwei Möglichkeiten für K:
* K ist ein Knoten, für den man noch nie einen Weg von S dorthin
betrachtet hat.Man hat jetzt erstmalig einen Weg von S dorthin
gefunden, nämlich über R und man kennt auch die Weglänge D.
Diese Weglänge schreibt man als Abstandsmarke in den Knoten K.
* Man kennt aus früheren Schritten bereits einen Weg nach K (über
einen anderen rot markierten Knoten R‘), dessen Weglänge D‘ als
Abstandmarke in diesem Knoten steht.
Durch Vergleich von D und D‘ erkennt man, ob der neue Weg über
R günstiger ist als der Weg über R‘.
Falls D kleiner als D‘ ist, ist der neue Weg günstiger und man
*schreibt D als neue Abstandmarke in den Knoten K
*entfernt den Bogen von R‘ nach K aus dem Graphen, da
sich dieser Weg als unrentabel herausgestellt hat.
Falls jetzt kein Bogen und keine Kante mehr von R‘ abgehen,
kann R‘ entfernt werden.Das gleiche geschieht mit vorherigen
Kanten und Bögen, bei der selben Bedingung.
Falls D‘ kleiner ist als D, dann bedeutet dass, dass der neue Weg uninteressant ist, da er länger ist als ein bereits gefundener und man
*behält die alte Abstandsmarke bei.
*entfernt den Bogen von R nach K aus dem Graphen.
Falls dadurch keine Bögen oder Kanten mehr von R abgehen
wird R gelöscht, das gleiche gilt für die vorigen Bögen und Kanten.
Falls D und D‘ identisch sind, sind beide nach K bekannten Wege gleichwertig und wir können uns für einen der beiden Wege entscheiden.
*Nun wählen wir uns von allen Knoten, die eine Abstandmarke tragen und
noch nicht rot mariert sind, denjenigen mit der geringsten Abstandmarke
aus (bei gleicher Abstandmarke einen beliebigen dieser Knoten)
Rot markierte Knoten bedeuten, dass wir zu ihnen schon einen kürzesten Weg gefunden haben, also müssen wir das ganze nur so lange tun, bis wir bei unserem Zielknoten Z angelangt sind.

Quellen
Als Quelle habe ich das Buch „Das Geheimnis des kürzesten Weges – Ein mathematisches Abenteuer“ von Peter Gritzmann und René Brandenberg genutz.
Zudem habe ich mich im Internet informiert.
Ich habe nicht zitiert sondern alles selbst formuliert. Das Buch und das Internet haben mir gezeigt, wie der Dijkstra-Algorithmus funktioniert, so dass ich mein Wissen in diese Facharbeit umgesetzt habe.
Ich erkläre, dass ich die Facharbeit ohne fremde Hilfe angefertigt und nur die im Literaturverzeichnis angeführten Quellen und Hilfsmittel benutzt habe.

Download: PDF, DOC