MuPAD Education Group: Kostenlose Materialen für MuPAD Pro:
www.sciface.com/education, schule.mupad.de, studium.mupad.de, mupad.zum.de.

________________________________________________________________________________

 

Inhalt....: Dijkstras Algorithmus

Kategorie.: Unterrichtsmaterial

Mathematik: Analysis, Numerik

MuPAD.....: 3.0.0

Datum.....: 2004-08-11

Autoren...: Tim Fischbach <mail@timfischbach.de>

________________________________________________________________________________

 

[Anmerkung: Die Definition der im folgenden verwendeten Routinen werden vorab

automatisch geladen. Siehe hierzu unter dem Menüpunkt: Datei - Eingenschaften...

- Initialisierungs-Kommandos. Im Web finden Sie die Dateien 'ServiceLayer.mu',

'StepByStepGenerator.mu', 'UIUtilities.mu' und 'Utilities.mu' im selben Verzeichnis

wie dieses Arbeitsblatt.]

 

Basiert auf einer Facharbeit im Fach Mathematik

Schuljahr 2001/02

September 2003

 

Tim Fischbach

Dijkstras Algorithmus

Kürzeste Wege im öffentlichen Nahverkehr

 

1 Einleitung

  1.1 Mathematik im Alltag

  1.2 Der öffentliche Nahverkehr und kürzeste Wege

2 Das Kürzeste-Wege-Problem

  2.1 Allgemeine Definition

  2.2 Anwendbarkeit

3 Dijkstras Algorithmus

  3.1 Allgemein

  3.2 Beispiel

  3.3 Theoretische Beschreibung

  3.4 Implementierung

  3.5 Schlussbemerkung

5 Appendix

  5.1 Literaturangaben

 

1 Einleitung

1.1 Mathematik im Alltag

Die Mathematik  vielen scheint sie fremd, fern, abstrakt. Mancher sieht in ihr ein

undurchschaubares Konstrukt, mit welchem Probleme gelöst werden können, die ohne sie

niemals entstanden wären; eine fremdartige Kunst, der strenge graue Herren in der

Wissenschaft geweihten Universitätsgebäuden mittels kryptischer Formeln frönen.

Doch ist die Mathematik wirklich derart irrelevant und praxisfremd? Wer ein solches Bild vor

Augen hat, löst die Mathematik völlig von ihren Anwendungsgebieten ab und verkennt, wie

stark der Mensch in seinem alltäglichen Leben von ihr umgeben ist. Schon bei den einfachsten

Entscheidungen sieht man sich mit Kernproblemen der Mathematik konfrontiert:

 

„Wie belade ich den Kofferraum meines Pkws am günstigsten, damit möglichst das

         gesamte Urlaubsgepäck hinein passt?"

 

„Wie plane ich den Wocheneinkauf, damit ich möglichst wenig hin- und herfahren muss?"

 

„Wie gehe ich beim Ausstechen der Weihnachtsplätzchen vor, damit ich den Teig

         möglichst selten aufs neue ausrollen muss?"

 

„Wie komme ich von dem Ort, an dem ich gerade stehe, am schnellsten mit der

          Straßenbahn zur Stadtmitte?"

 

Allen diesen Fragen liegt ein Optimierungsproblem zu Grunde. Es geht um

Verschnittoptimierungen, kürzeste Wege und Ähnliches.

 

Da der Mensch diese Probleme oftmals eher assoziativ und spontan löst, erzielt er sicherlich

nicht immer den höchsten Grad der Optimierung. In vielen Fällen kann daher der Einsatz

mathematischer Verfahren den Entscheidungsprozess unterstützen. Beispielhaft wären hier

Fahrplanautomaten zu nennen, die den Kunden nach Eingabe seines Zieles über die günstigsten

Anschlüsse informieren.

 

Nachdem nun klar geworden ist, dass mathematische Problemstellungen im Alltag nicht

selten sind, soll in den nächsten Abschnitten ein einzelner Fall ausgewählt, ein

mathematischer Lösungsweg vorgestellt und dieser in MuPAD umgesetzt werden. Die interaktive

Einflussnahme des Lesers auf die beispielhaft erläuterten Szenarien, soll ein spielerisches

Kennenlernen der Arbeitsweise des Algorithmus ermöglichen.

 

1.2 Der öffentliche Nahverkehr und kürzeste Wege

Konzentrieren wir uns nun auf das vierte Beispiel des vorherigen Abschnittes. Die Frage nach der

kürzesten öffentlichen Nahverkehrsverbindung ist  selbst wenn jeder sie sich oder einem

anderen schon einmal gestellt haben dürfte  nicht immer ganz einfach zu beantworten.

Oftmals ist das Erreichen der Zielhaltestelle über verschiedene Linien möglich. Außerdem

können ganz verschiedene Faktoren optimiert werden: Soll die Fahrt möglichst günstig sein,

soll das Umsteigen vermieden werden oder steht eine besonders kurze Fahrzeit im Mittelpunkt

der Betrachtung.

 

2 Das Kürzeste-Wege-Problem

2.1 Allgemeine Definition

Alle genannten Szenarien lassen sich auf ein Modell zur Untersuchung der kürzesten Strecken

zurückführen. Diese verallgemeinerte Problemstellung nennt sich Single Source Shortest

Path Problem (oder kurz SSSP, das zweite P entfällt bei dieser Schreibweise).

 

 

Abbildung 2.1-1

 

Dazu wird aus der konkreten Vorgabe ein Graph gebildet, der sich aus Knoten und Kanten

zusammensetzt (siehe Abb. 2.1-1). Die Knoten stellen dabei in unserem Beispiel die Haltestellen

dar und die Verbindungen zwischen diesen werden durch Kanten repräsentiert. Zusätzlich wird

jeder Kante ein Gewicht zugeordnet, welches z. B. eine geographische Entfernung zwischen

den Knoten, jedoch ebenfalls Fahrzeiten oder Fahrpreise ausdrücken kann. Als Gewicht sind

ausschließlich positive Werte zulässig. Kanten können der Einfachheit halber vorerst in beiden

Richtungen durchlaufen werden, es ist allerdings auch denkbar, mit gerichteten Kanten  zu

arbeiten. Die Knoten können beliebig  auch zirkulär  mit einander verbunden sein.

 

Das zu lösende Problem besteht nun darin, den Weg mit dem geringsten Gewicht zu finden, der

zwei im Voraus festgelegte Knoten miteinander verbindet. Das Gewicht eines Weges ergibt sich

dabei aus der Summe der Gewichte der durchlaufenen Kanten.

 

Definition 2.1-1:

Gegeben: Graph G = (V, E)

(Knotenmenge V, Kantenmenge E)

          Nicht negative Gewichte wuv für alle Kanten uv  E

            Zwei Knoten s, t

Gesucht: Ein kürzester Weg von s nach t in G

 

2.2 Anwendbarkeit

Mittels dieser Abstraktion lassen sich erstaunlich viele Szenarien modellieren. Hier einige

Beispiele aus dem Umfeld des öffentlichen Nahverkehrs:

 

Standardanordnung

Der Normalfall, mit einer festgelegten Anzahl von Haltestellen und bidirektionalen

Verbindungen, stellt die einfachste Anforderung dar. Dabei ist das Gewicht eines Weges

von einer Haltestelle zu einer anderen unabhängig von der Richtung, in die man sich bewegt.

Das heißt pro Kante ist nur ein Gewicht festlegbar, welches für beide Durchlaufrichtungen

gültig ist.

 

Verbindungen für nur eine Fahrtrichtung

 

Abbildung 2.2-1

 

Allerdings ist es auch denkbar, dass eine Kante nur in einer Richtung durchlaufen werden

kann. Führt eine Straßenbahnlinie z. B. durch eine Einbahnstraße, so kann es vorkommen,

dass Bahnen in Gegenrichtung einen Umweg durch eine andere Straße fahren müssen.

Folglich werden manche Haltestellen nur in einer Richtung angefahren oder es nehmen

Fahrten zwischen zwei Haltestellen abhängig von der Fahrtrichtung unterschiedlich viel Zeit in

Anspruch.

 

Zur Umsetzung dieses Szenarios müssen die Kanten gerichtet sein, d.h. nur eine

Durchlaufrichtung zulassen. Eine ungerichtete Kante kann dann durch zwei entgegengesetzt

gerichtete Kanten dargestellt werden. In Abbildung 2.2-1 ist ein entsprechender Aufbau

abgebildet.

 

Wabenbasierte Tarifsysteme

 

Abbildung 2.2-2

 

Viele Verkehrsbetriebe berechnen ihre Fahrpreise durch Einteilung des Stadtgebiets in Waben.

Es fallen dann jeweils Kosten beim Erreichen einer neuen Wabe an. Im Rahmen unseres

Modells ist es ein Leichtes diese Anordnung umzusetzen. Alle Kanten, die Knoten innerhalb

der selben Wabe verbinden, werden mit einem Gewicht gleich Null definiert. Nur

wabengrenzen-überschreitenden Kanten wird ein Gewicht zugeordnet.  Abbildung 2.2-2 stellt

diesen Sachverhalt beispielhaft dar.

 

Umsteigen vermeiden

 

Abbildung 2.2-3

 

Es wäre ebenfalls interessant, eine Verbindung zu finden, bei der der Fahrgast den Weg von

der Starthaltestelle zur Zielhaltestelle möglichst mit einer einzelnen Straßenbahnlinie

zurücklegen kann oder wenigstens möglichst selten umsteigen muss. Zur Ermittlung dieses

Weges, bedarf es eines völlig anderen Aufbaus des Graphen: So kann z. B. die Anzahl der

Knoten, die eine Haltestelle repräsentieren, von eins auf die Zahl der Straßenbahnlinien, die

an dieser Haltestelle halten, hochgesetzt werden. Allen Kanten, die von einer Station zur

nächsten führen, kann man dann das Gewicht 0 zuweisen und ausschließlich denen, die

verschiedene Linien an einer einzelnen Haltestellen miteinander verknüpfen, das Gewicht 1

geben. Auf diese Weise erhöht sich das Gewicht eines Weges nur, wenn der Fahrgast an

einer Haltestelle die Straßenbahnlinie wechselt, sich also über Kanten bewegt, die innerhalb

einer Haltestelle verschiedene Linien miteinander verbinden. Zusätzlich muss man für jede

Haltestelle noch einen weiteren Knoten definieren, der von allen anderen Knoten der

Haltestelle aus über gerichtete Kanten mit dem Gewicht 0 zu erreichen ist und als Zielknoten

fungiert, wenn der Weg mit dem geringsten Gewicht zur Station gesucht wird. Dies ist nötig,

weil die übrigen Knoten nicht als Zielknoten eingesetzt werden können. Gäbe man nämlich

einen der anderen als Zielknoten an, so würde beim Erreichen der Haltestelle über eine

Straßenbahnlinie, die möglicherweise nicht über diesen Zielknoten führt, ein weiterer

Linienwechsel verzeichnet, der in Wirklichkeit nicht betrachtet werden darf, da die Haltestelle

ja bereits erreicht und die Fahrt beendet ist. Der Weg zum Zusatzknoten wird hingegen nicht

als Umsteigen vermerkt, da die zu ihm führenden Kanten das Gewicht 0 besitzen. Die

Abbildung 2.2-3 verdeutlicht diesen recht komplexen Aufbau.

 

Die vier Beispiele machen klar, dass die vorgenommene Verallgemeinerung dem ursprünglichen

Problem also anscheinend in seiner ganzen Vielseitigkeit gerecht wird. Daher können wir uns nun

einem Lösungsansatz zuwenden.

 

3 Dijkstras Algorithmus

3.1 Allgemein

Einen heutzutage gängigen Weg zur Berechnung kürzester Strecken in Graphen stellt ein 1959

vom Mathematiker Edsger Wybe Dijkstra vorgeschlagener Algorithmus dar, der unter dem

Namen „Dijkstras Algorithmus" bekannt geworden ist. Er basiert auf einem Algorithmus von

L.R. Ford Jr. aus dem Jahre 1956, dessen Grundideen er übernimmt:

 

Es ist aus Sicht des Algorithmus nicht aufwendiger die kürzesten Wege von einem Knoten des

Graphen zu allen anderen zu bestimmen, als einen kürzesten Weg von einem Start- zu einem

Zielknoten zu finden. Die Angabe des Endknotens kann eventuell genutzt werden, um die

Berechnung aller kürzesten Wege abzubrechen, nachdem der Endknoten erreicht wurde.

Ansonsten endet der Vorgang, wenn alle Knoten entdeckt sind.

 

Im Verlauf der Ausführung ermittelt der Algorithmus für jeden Knoten des ihm übergebenen

Graphs zwei Angaben: Nämlich das  Gewicht des kürzesten Weges vom Startpunkt aus und

jeweils einen Verweis auf den vorhergehenden Knoten über den dieser kürzeste Weg verläuft.

 

3.2 Beispiel

Um die Funktionsweise des Algorithmus genauer zu erläutern, soll eine einzelne Anordnung der

Knoten und Kanten herangezogen und deren Verarbeitung schrittweise dargestellt werden. Den

Aufbau des im Beispiel untersuchten Szenarios kann der Leser selbst durch Manipulation der

folgenden Eingaberegion bestimmen. Die Kanten sind gerichtet - können also nur in der angegebenen

Richtung durchlaufen werden.

 

Benutzungshinweis: Die folgende Eingaberegion dient der Festlegung des zu untersuchenden

Graphs. Ein Großteil der eingegebenen Informationen bezieht sich ausschließlich auf die graphische

Präsentation der Anordnung im Rahmen dieses Dokuments. Eigenschaften der Knoten wie Position

oder Beschriftung haben keinerlei Relevanz für Dijkstras Algorithmus, sie stellen lediglich eine

leserfreundliche Darstellung der Zwischenergebnisse sicher. Die Gewichte der Kanten stehen in

keinem Verhältnis zu deren geometrischer Länge.

 

Varieren Sie den Code entsprechend folgender Regeln, um den Graph festzulegen:

- Verändern Sie nicht die Aufrufe der Prozeduren 'szenarioZuruecksetzen(...)' und

'schrittFuerSchrittBeipielAusgeben()' in der ersten und letzten Zeile der Eingaberegion.

 

- Stellen Sie sicher, dass für jeden Knoten, der Teil der untersuchten Anordnung sein soll, ein Aufruf

der Prozedur 'knotenHinzufuegen(...)' existiert. Die Parameter haben folgende Bedeutung:

   knotenHinzufügen(name,  position)

name := eine im Rahmen des Szenarios eindeutige Zeichenfolge

position := [x, y]: Liste (DOM_LIST) mit zwei Elementen des Domaintyps DOM_INT, die

   die Koordinaten darstellen

Es muss mindestens ein Knoten festgelgt werden.

 

- Stellen Sie sicher, dass für jede Kante, die Teil der untersuchten Anordnung sein soll, ein Aufruf

der Prozedur 'kanteHinzufuegen(...)' existiert. Die Parameter haben folgende Bedeutung:

   kanteHinzufügen(nameAusgangsknoten, nameZielknoten, gewicht)

nameAusgangsknoten := Zeichenfolge mit dem Namen des Knotens, von dem die Kante ausgehen soll

nameZielknoten := Zeichenfolge mit dem Namen des Knotens, der über die Kante erreicht

   werden kann

gewicht := Gewicht der Kante als Wert des Domaintyps DOM_INT

nameAusgangsknoten und nameZielknoten dürfen nicht übereinstimmen.

 

- Stellen Sie sicher, dass der Prozedur 'startKnotenFestlegen(...)' als Parameter eine Zeichenfolge mit dem

Namen des Startknotens übergeben wird.

 

Um das Schritt-für-Schritt-Beispiel zu generieren, positionieren Sie das Eingabe-Caret in der Eingaberegion

und drücken Sie die Enter-Taste (bzw. Shift-Enter, je nach Einstellung).

 

Doppelklicken Sie auf eine der ausgegebenen Abbildungen, um in den Animationsmodus zu wechseln und die

im entsprechenden Schritt bisher bekannten kürzesten Wege zu den Knoten nacheinander, farblich hervorgehoben

anzeigen zu lassen.

 

Standard: Falls der Code in einen ungültigen Zustand gekommen sein sollte, der von Ihnen nicht

behoben werden kann, ersetzen Sie den gesamten Code in der Eingaberegion durch den nachfolgend

abgedruckten Standardcode, um wieder einen funktionsfähigen Ausgangszustand herzustellen:

 

szenarioZuruecksetzen():                 // Erforderlicher Prozeduraufruf: Diese Zeile nicht verändern.

 

knotenHinzufuegen("v1", [10, 10]):

knotenHinzufuegen("v2", [0, 10]):

knotenHinzufuegen("v3", [0, 0]):

knotenHinzufuegen("v4", [10, 0]):

 

kanteHinzufuegen("v1", "v2", 2):

kanteHinzufuegen("v1", "v3", 5):

kanteHinzufuegen("v2", "v3", 2):

kanteHinzufuegen("v3", "v4", 1):

 

startKnotenFestlegen("v1"):

schrittFuerSchrittBeispielAusgeben():    // Erforderlicher Prozeduraufruf: Diese Zeile nicht verändern

 

Eingaberegion 3.2-1:

 

         

3.3 Theoretische Beschreibung

Nachdem grundsätzlich die Funktionsweise des Algorithmus klar geworden sein sollte, gilt es

nun die Darstellung des Ablaufs technisch zu konkretisieren. Dabei wollen wir uns ausgehend

vom vorherigen Beispiel der später eingeführten, in MuPAD codierten Implementierung in

einigen analysierenden Überlegungen annähern.

 

Eingangswerte

Zunächst stellt sich die Frage, welche Parameter dem Algorithmus übergeben werden müssen.

Betrachtet man die Arbeitsweise genauer, so lässt sich diese Information leicht ableiten:

Startknoten: s

Zur Ausführung des Algorithmus ist die Angabe des Startknotens nötig. s ist der Index

des Startknotens.

Kostenmatrix: C(v2, v1)

Außerdem ist das Wissen um die Kantengewichte unentbehrlich: Beim Vergleich zweier

alternativer Wege, bei welchem die Entfernung des selektierten Knotens zu seinen

Nachbarknoten wichtig ist, bedient sich der Algorithmus dieser Information.

 

Zur effektiven  Handhabung werden die Eigenschaften der - bei der Festlegung des

Beispielgraphs noch separat definierten - Knoten und Kanten zu einem einzigen

Parameter zusammengefasst: Der Kostenmatrix. Dies ist möglich, da keine weiteren

Informationen über die Knoten übergeben werden müssen. Name und Position sind

für den Algorithmus irrelevant.

 

Diese quadratische Matrix weist für jeden Knoten eine Spalte und eine Zeile auf.  Die

Werte der Matrix entsprechen den Gewichten der Kanten, die die aus Zeilen- und Spaltenindex

ablesbaren Knoten mit einander verbinden. Eine Spalte beinhaltet dabei die Gewichte der

Kanten, die den Knoten, dessen Index dem Spaltenindex entspricht, als Ausgangsknoten

festgelegt haben. Eine Zeile der Matrix beherbergt folglich die Gewichte der Kanten, über die

der Knoten, dessen Index dem Zeilenindex entspricht, erreicht werden kann. Existiert keine

entsprechende Kante ist der Wert der Matrix an dieser Position +.

 

Benutzungshinweis: Führen Sie den Code der folgenden Eingaberegion aus, um eine

aus den Angaben des Schritt-Für-Schritt-Beispiels generierte Kostenmatrix,

wie sie dem Algorithmus übergeben wird, anzuzeigen. Der Code in Eingaberegion 3.2-1

muss mindestens einmal seit dem Öffnen der Datei ausgeführt worden sein.

 

 

Eingaberegion 3.3-1:

 

Datenstruktur

In seinem Inneren muss der Algorithmus mehrere Variablen halten, um Informationen über die Wege

zu den Knoten nachzuhalten. Welche das sein müssen, ergibt sich aus den Formulierungen des

Beispiels:

 

"Gewicht des bisher bekannten kürzesten Weges vom Startknoten": D[v]

Die Werte, die in den Abbildungen des Beispiels (siehe Abschnitt 3.2) hinter den Namen der

Knoten abgedruckt sind und das Gewicht der bisher bekannten kürzesten Verbindung mit dem

Startknoten darstellen, werden vom Algorithmus in einer eindimensionalen Matrix verwaltet.

Die Anzahl der Einträge richtet sich nach der Zahl der Knoten des Graphs.

 

"Vorgängerknoten": P[v]

Die Verweise auf einen Vorgängerknoten, die in den Beispielabbildungen hinter den Knotennamen

ausgeschrieben sind, hält der Algorithmus in einer weiteren eindimensionalen Matrix. Auch hier

entspricht die Länge von P der Anzahl der Knoten im Graph. Es wird für jeden Knoten der Index

des Vorgängerknotens gespeichert.

 

Des weiteren bedarf es einiger Variablen, die Informationen über den inneren Zustand des Algorithmus

aufnehmen. Auch diese lassen sich aus den Formulierungen des Beispiels ableiten:

 

"Permanent markierte Knoten": S

Im Verlauf der Ausführung werden immer weitere Knoten permanent markiert, d.h. der

bisher ermittelte Weg als der kürzest mögliche festgeschrieben. Um zu speichern welche Knoten

bereits permanent markiert sind, bietet sich die Benutzung einer Auflistung an, der dynamisch

Einträge hinzugefügt werden können. Dieser Auflistung geben wir den Namen S. Wird ein Knoten

permanent markiert, so wird ein seinem Index entsprechender Wert zu S hinzugefügt.

 

"Selektierter Knoten": u

Schließlich bleibt noch die Variable, die den Index des selektierten Knotens aufnimmt.

Wir nennen sie u.

 

Zusätzlich vereinfacht noch eine weitere lokale Variable die Durchführung des Aktualisierungsschrittes:

 

Nachbar-Zuordnungs-Array A[v]

Nachdem ein neuer Knoten permanent markiert wurde, werden die kürzesten Wege zu den

Nachbarknoten überprüft. Dazu muss der Algorithmus allerdings Kenntnis davon haben,

welche Knoten benachbart sind. Diese Information kann leicht aus der Kostenmatrix abgeleitet

werden: Ein Knoten x ist mit einem Knoten y benachbart, falls der Wert der Kostenmatrix an der

Position (y, x) kleiner als unendlich ist. x und y dürfen bei dieser Betrachtung nicht übereinstimmen.

Aus Gründen der einfacheren Handhabung, wird vor Ausführung des Algorithmus ein Array erzeugt,

welches für jeden Knoten eine Liste mit den Indizes der benachbarten Knoten beinhaltet.

 

Benutzungshinweis: Führen Sie den Code der folgenden Eingaberegion aus, um ein

aus den Angaben des Schritt-Für-Schritt-Beispiels generiertes Nachbar-Zuordnungs-Array,

wie es der Algorithmus generiert, anzuzeigen. Der Code in Eingaberegion 3.2-1

muss mindestens einmal seit dem Öffnen der Datei ausgeführt worden sein.

 

Eingaberegion 3.3-2:

 

Vorgänge

Betrachtet man das Beispiel genauer, so fällt auf, dass sich die nach der Initialisierung

verrichteten Arbeiten stets wiederholen. Verallgemeinernd lässt sich der Ablauf also unter

Benutzung der oben definierten Variablen vereinfacht darstellen.

 

In der Initialisierungsphase werden folgende Schritte durchgeführt:

1. Für jeden Knoten wird die Entfernung vom Startknoten auf   gesetzt. D[k] = , wobei k

   der Index des Knotens ist.

 

2. Die Entfernung des Startknotens s von sich selbst wird gleich 0 festgelegt. D[s] = 0.

 

Im Hauptteil führt der Algorithmus solange die folgenden zwei Schritte aus, bis alle Knoten

permanent markiert sind:

1. Es wird nach einem Knoten gesucht, dessen Index (u) noch nicht Mitglied von S ist und dessen bisher

    bekannter kürzester Weg vom Startknoten das geringste Gewicht hat (D[u]). Der index des Knotens (u)

    wird zu S hinzugefügt. Es kann keinen kürzeren Weg zum Knoten über einen noch nicht permanent

    markierten Knoten mit dem Index x geben, denn dazu müsste D[x]<D[u] sein, wodurch x vor u

    permanent markiert worden wäre.

 

2. Als nächstes wird für jeden Knoten, dessen Index k Mitglied von A[u] ist und noch nicht zu S hinzugefügt

    wurde, überprüft, ob der Weg vom Startknoten über u nach k kürzer ist als der bisher festgelegte Weg

    nach k (D[u]+C[k, u] < D[k]). Ist dies der Fall, so wird D[k] und der Verweis auf den Vorgängerknoten

    (P[k] = u) aktualisiert.

 

Rückgabewert

Nach Abschluss der Ausführung gibt der Algorithmus die Matrizen D und P als Ergebnis zurück.

Aus ihnen kann für jeden Knoten der kürzeste Weg vom Startknoten rekonstruiert werden.

 

3.4 Implementierung

Um die Erläuterungen dieses Kapitels abzurunden, stellt die nun folgende MuPAD-Implementierung die

Arbeitsweise Dijkstras Algorithmus noch einmal kompakt dar. Die Benennungen sind aus dem

vorherigen Abschnitt übernommen.

 

dkstr := proc(s : DOM_INT     /* Startknotenindex */,

              C : Dom::Matrix /* Kostenmatrix */)

 

name DijkstrasAlgorithmus;

 

local n  /* Anzahl der Knoten */,

      A  /* Nachbarknotenzuordnungsliste */,

      D  /* Längen der bisher bekannten kürzesten Wege */,

      P  /* Vorgängerknotenindizes */,

      S  /* Permanent markierte Knoten */,

      u  /* Index des selektierten Knotens*/,

      k  /* Index des überprüften Nachbarknotens */,

      dw /* Hilfsvariable */,

      i  /* Iterationsvariable */;

 

begin

  // Initialisierung

 

  n := sqrt(nops(C));

  A := erzeugeNachbarknotenZuordnungsMatrixAusC(C);

  D := array(1..n);

  P := array(1..n);

  S := [];

 

  for i from 1 to n do

    D[i] := infinity;

  end_for;

 

  D[s] := 0;

  P[s] := s;

  // Hauptteil

 

  while TRUE do

    dw := infinity;

 

    for i from 1 to n do

      if contains(S, i) <= 0 and D[i] < dw then

        u := i;

        dw := D[i];

      end_if;

    end_for;

 

    if dw = infinity then break end_if;

    S := append(S, u);

 

    for i from 1 to nops(A[u]) do

      k := A[u][i];

 

      if contains(S, k) <= 0 then

        if D[u] + C[u, k] < D[k] then

          D[k] := D[u] + C[u, k];

          P[k] := u;

        end_if;

      end_if;

    end_for;

  end_while;

 

  return ([D, P]);

end_proc:

 

Benutzungshinweis: Führen Sie den Code der folgenden Eingaberegion aus, um den

in Eingaberegion 3.2-1 definierten Graph untersuchen und Zwischenergebnisse

unter Benutzung der Bezeichnungen aus Abschnitt 3.3 ausgeben zu lassen. Der Code

in Eingaberegion 3.2-1 muss mindestens einmal seit dem Öffnen der Datei ausgeführt

worden sein. Seit dem letzten Schritt veränderte Arrayeinträge sind mit einem *

gekennzeichnet.

 

 

Eingaberegion 3.4-1:

3.5 Schlussbemerkung

Die Besprechung des Algorithmus hat gezeigt, dass mathematische Verfahren versuchen

Antworten auf durchaus praxisbezogene und zum Teil sogar alltägliche Problemstellungen zu

finden, auch wenn dieser vertraute Hintergrund durch Abstraktion und Verallgemeinerung

oftmals erst auf den zweiten Blick zu erkennen ist.

 

Wenn Sie also das nächste Mal einen Einkaufsbummel durch die Stadt vorhaben, der mit einer

Straßenbahnfahrt beginnt, so sollte mittels Dijkstras Algorithmus der Planung einer optimalen

Anfahrtsroute nichts mehr im Wege stehen. Bleibt nur zu hoffen, dass nicht Verspätungen und

Verkehrsbehinderungen Sie unsanft aus den Idealen der Theorie in das unorganisierte Gedränge

der Realität zurückholen...

 

5 Appendix

5.1 Literaturangaben

1. Borndörfer, Ralf; Grötschel, Martin; Löbel, Andreas; „Der schnellste Weg zum Ziel"; in

   M. Aigner und E. Behrends (Hrsg.); „Alles Mathematik: Vom Pythagoras zum CD-Player";

   Vieweg Verlag; 2000

 

2. www.cs.rochester.edu/users/faculty/nelson/courses/csc_173/graphs/sssp.html

 

________________________________________________________________________________

 

Anmerkungen:

 

1.  Weitere Anregungen finden Sie unter: http://schule.mupad.de bzw. http://studium.mupad.de

________________________________________________________________________________

 

MuPAD Education Group: Kostenlose Materialen für MuPAD Pro:
www.sciface.com/education, schule.mupad.de, studium.mupad.de, mupad.zum.de.