Der Algorithmus von Dijkstra

Minimale Abstände und kürzeste Wege in gewichteten Graphen

In gewichteten Graphen wird üblicherweise der Abstand zwischen zwei Knoten über die Gewichte der Kanten festgelegt. Der Abstand zweier Knoten längs eines Weges ergibt sich als Summe der Gewichte der Kanten, die den Weg bilden.

Die Bestimmung minimaler Abstände und kürzester Wege kann ähnlich zu dem Verfahren des letzten Abschnitts erfolgen.

Aufgabe 1

Die Abbildungen zeigen ein Verfahren, wie man systematisch minimale Abstände und kürzeste in einem gewichteten Graphen ermitteln kann.

Versuche, anhand der Abbildungen das Verfahren zu erschließen und folgende Fragen zu klären: Welche Knoten werden jeweils grün / blau markiert? Wie werden die zu verarbeitenden Knoten ausgewählt? Wie kommen die Zahlen (als Zusatzinformationen an den Knoten) zustande? Warum müssen Zahlen manchmal auch abgeändert werden? Warum hört das Verfahren nach der letzten Abbildung auf? Wie ist das Ergebnis zu deuten?

Der Algorithmus zum Verfahren - Algorithmus von Dijkstra

Das Verfahren zur Bestimmung kürzester Wege in gewichteten Graphen verarbeitet Graphen ähnlich wie der Algorithmus von Moore. Genau wie beim Algorithmus von Moore wird der Graph in einem ersten Schritt vorbereitet:

Jeder Knoten wird mit Zusatzinformation versehen, die den aktuellen Kenntnisstand über Abstand und Herkunft eines kürzesten Weges beschreiben.

Die eigentliche Verarbeitung erfolgt ähnlich wie beim Algorithmus von Moore:

Bei der Wahl des nächsten zu verarbeitenden Knotens wird hier der Knoten aus der Liste (grün) ausgewählt, der bis zu diesem Verarbeitungsschritt einen minimalen Abstand zum Startknoten aufweist. Im vorliegenden Fall ist das der Knoten E. Von diesem Knoten aus werden alle noch nicht verarbeiteten Nachbarknoten berücksichtigt (hier D und G). Wenn diese noch nicht in der Liste der noch zu verarbeitenden Knoten liegen (wie D), dann werden die Zusatzinformationen neu gesetzt. Wenn sie bereits in der Liste der noch zu verarbeitenden Knoten vorkommen (wie G), dann wird überprüft, ob es einen kürzeren Weg über den ausgewählten Knoten gibt. Im vorliegenden Fall ist der Weg vom Startknoten A zum Knoten G über den Knoten E kürzer als direkte Weg von A nach G. Daher werden hier die Zusatzinformationen entsprechend abgeändert.

Dieses Verfahren bildet die Grundlage des Algorithmus von Dijkstra:

ALGORITHMUS # von Dijkstra
Übergabedaten: Graph, startKnoten, zielKnoten
# Vorbereitung des Graphen
für alle knoten des Graphen:
    setze abstand auf 'u'
    setze herkunft auf None
setze abstand von startKnoten.abstand auf 0
füge startKnoten in eine Liste zuVerarbeiten ein
# Verarbeitung der Knoten
SOLANGE die Liste zuVerarbeiten nicht leer ist:
    bestimme einen Knoten minKnoten aus zuVerarbeiten mit minimalem Abstand
    entferne minKnoten aus zuVerarbeiten
    für alle nachbarKnoten von minKnoten:
        gewicht = Gewicht der Kante von minKnoten zu nachbarKnoten
        neuerAbstand = (abstand von minKnoten) + gewicht
        WENN abstand von nachbarKnoten == 'u':
            füge nachbarKnoten in die Liste zuVerarbeiten ein (z.B. am Listenende)
            setze abstand von nachbarKnoten auf neuerAbstand
            setze herkunft von nachbarKnoten auf minKnoten
        SONST:
            WENN nachbarKnoten in zuVerarbeiten liegt:
                WENN abstand von nachbarKnoten > neuerAbstand:
                    setze abstand von nachbarKnoten auf neuerAbstand
                    setze herkunft von nachbarKnoten auf minKnoten
weglaenge = abstand von zielKnoten
# Erzeugung des Weges zum zielKnoten
weg = []
knoten = zielKnoten    
SOLANGE knoten != startKnoten und herkunft von knoten != None:
    weg = [(herkunft von knoten, knoten)] + weg
    knoten = herkunft von knoten
Rückgabedaten: (weg, weglaenge)

Aufgabe 2

Führe den Algorithmus mit F als Startknoten aus. Als Hilfe kannst du dir ein Arbeitsblatt mit leeren Graphen ausdrucken.