inf-schule | Kürzeste Wege in Graphen

Implementierung

Implementierung des Algorithmus von Moore

Hier noch einmal der Algorithmus von Moore:

ALGORITHMUS # von Moore
Ü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 Schlange zuVerarbeiten ein
# Verarbeitung der Knoten
SOLANGE die Schlange zuVerarbeiten nicht leer ist:
    ausgewaehlterKnoten ist das erste Element aus zuVerarbeiten
    entferne ausgewaehlterKnoten aus zuVerarbeiten 
    für alle nachbarKnoten von ausgewaehlterKnoten:
        wenn abstand von nachbarKnoten == 'u':
            füge nachbarKnoten hinten in die Schlange zuVerarbeiten ein
            neuerAbstand = (abstand von ausgewahlterKnoten) + 1
            setze abstand von nachbarKnoten auf neuerAbstand
            setze herkunft von nachbarKnoten auf ausgewaehlterKnoten
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)

Die folgende Implementierung dieses Algorithmus beruht auf einer Darstellung von Graphen mit Nachbarschaftlisten.

def existiertKnoten(graph, knoten):
    ergebnis = False
    for eintrag in graph:
        if eintrag[0] == knoten:
            ergebnis = True
    return ergebnis

def getAlleKnoten(graph):
    knotenListe = []
    for eintrag in graph:
        knotenListe = knotenListe + [eintrag[0]]
    return knotenListe

def getAlleNachbarn(graph, knoten):
    nachbarListe = []
    for eintrag in graph:
        if eintrag[0] == knoten:
            nachbarListe = eintrag[1]
    return nachbarListe

def getAbstand(erweiterterGraph, knoten):
    ergebnis = None
    for eintrag in erweiterterGraph:
        if eintrag[0] == knoten:
            ergebnis = eintrag[1]
    return ergebnis

def getHerkunft(erweiterterGraph, knoten):
    ergebnis = None
    for eintrag in erweiterterGraph:
        if eintrag[0] == knoten:
            ergebnis = eintrag[2]
    return ergebnis
    
def setAbstand(erweiterterGraph, knoten, wert):
    erweiterterGraphNeu = []
    for eintrag in erweiterterGraph:
        if eintrag[0] == knoten:
            eintragNeu = [eintrag[0], wert, eintrag[2], eintrag[3]]
            erweiterterGraphNeu = erweiterterGraphNeu + [eintragNeu]
        else:
            erweiterterGraphNeu = erweiterterGraphNeu + [eintrag]
    return erweiterterGraphNeu

def setHerkunft(erweiterterGraph, knoten, wert):
    erweiterterGraphNeu = []
    for eintrag in erweiterterGraph:
        if eintrag[0] == knoten:
            eintragNeu = [eintrag[0], eintrag[1], wert, eintrag[3]]
            erweiterterGraphNeu = erweiterterGraphNeu + [eintragNeu]
        else:
            erweiterterGraphNeu = erweiterterGraphNeu + [eintrag]
    return erweiterterGraphNeu

def initErweiterterGraph(graph, startKnoten):
    erweiterterGraph = []
    for eintrag in graph:
        if eintrag[0] == startKnoten:
            eintragNeu = [eintrag[0], 0, None, eintrag[1]]
            erweiterterGraph = erweiterterGraph + [eintragNeu]
        else:
            eintragNeu = [eintrag[0], 'u', None, eintrag[1]]
            erweiterterGraph = erweiterterGraph + [eintragNeu]
    return erweiterterGraph

def kuerzesterWegMoore(graph, startKnoten, zielKnoten):
    if existiertKnoten(graph, startKnoten) and existiertKnoten(graph, zielKnoten):
        # Vorbereitung
        erweiterterGraph = initErweiterterGraph(graph, startKnoten)
        zuVerarbeiten = [startKnoten]
        # Verarbeitung der Knoten
        while zuVerarbeiten != []:
            # bestimme einen Knoten ausgewaehlterKnoten aus zuVerarbeiten
            ausgewaehlterKnoten = zuVerarbeiten[0]
            # entferne ausgewaehlterKnoten aus zuVerarbeiten
            zuVerarbeiten = zuVerarbeiten[1:]
            # bearbeite die Nachbarn von ausgewaehlterKnoten
            for nachbarKnoten in getAlleNachbarn(graph, ausgewaehlterKnoten):
                if getAbstand(erweiterterGraph, nachbarKnoten) == 'u':
                    zuVerarbeiten = zuVerarbeiten + [nachbarKnoten]
                    neuerAbstand = getAbstand(erweiterterGraph, ausgewaehlterKnoten)+ 1
                    erweiterterGraph = setAbstand(erweiterterGraph, nachbarKnoten, neuerAbstand)
                    erweiterterGraph = setHerkunft(erweiterterGraph, nachbarKnoten, ausgewaehlterKnoten)
            weglaenge = getAbstand(erweiterterGraph, zielKnoten)  
        # Erzeugung des Weges zum zielKnoten
        weg = []
        knoten = zielKnoten    
        while knoten != startKnoten and getHerkunft(erweiterterGraph, knoten) != None:
            weg = [(getHerkunft(erweiterterGraph, knoten), knoten)] + weg
            knoten = getHerkunft(erweiterterGraph, knoten)      
    else:
        weg = []
        weglaenge = 'u'
    return (weg, weglaenge)

# Erzeugung des Testgraphen
testgraph_ohne_gewichte = \
[
['A', ['C', 'E', 'G']],
['B', ['C', 'D']],
['C', ['A', 'D', 'E']],
['D', ['B', 'E']],
['E', ['D', 'G']],
['F', ['B', 'D', 'H']],
['G', ['D']],
['H', ['F', 'G']]
]

# Test des Moore-Algorithmus
start = 'A'
ziel = 'B'
print('kürzester Weg von', start, 'nach', ziel, ':')
(weg, laenge) = kuerzesterWegMoore(testgraph_ohne_gewichte, start, ziel)
for w in weg:
    print(w)
print('Weglänge:', laenge)

Aufgabe 1

(a) Teste zunächst separat die Funktion initErweiterterGraph. Was leistet diese Funktion? Teste auch die Funktionen getAbstand, getHerkunft, setAbstand und setHerkunft?

(b) Ergänze Ausgaben in der Funktion kuerzesterWegMoore so, dass die Verarbeitung des Graphen Schritt für Schritt (wie in den Abbildungen im Abschnitt Der Algorithmus von Moore) nachvollzogen werden kann.

Aufgabe 2

Eine weitere Implementierung des Algorithmus von Moore findest du in der Klasse GraphMoore (siehe graph_moore.txt).

Objekte der Klasse GraphMoore stellen die Operation kuerzesterWegMoore zur Verfügung, mit der man Wege mit geringster Anzahl von Zwischenknoten in Graphen bestimmen kann.

Teste auch diese Implementierung des Algorithmus von Moore. Das folgende Testprogramm verdeutlicht die Verwendung der Klasse GraphMoore am Demo-Graphen graph_ohne_gewichte.xml.

from graph_moore import *

# Erzeugung des Graph-Objekts
g = GraphMoore()
# Erzeugung der Knoten und Kanten aus einer GraphML-Datei
datei = open("graph_ohne_gewichte.xml", "r")
xml_quelltext = datei.read()
g.graphmlToGraph(xml_quelltext) 
# Kontrollausgabe des Graphen
print('Graph:')
for knoten in g.getAlleKnoten():
    print(knoten, ':', g.getAlleNachbarn(knoten))
print()
# Test des Moore-Algorithmus
start = 'A'
ziel = 'B'
print('kürzester Weg von', start, 'nach', ziel, ':')
(weg, laenge) = g.kuerzesterWegMoore(start, ziel)
for w in weg:
    print(w)
print('Weglänge:', laenge)

Implementierung des Algorithmus von Dijkstra

Der Algorithmus von Dijkstra lässt sich so formulieren:

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 3

Mit den Hilfsfunktionen initErweiterterGraph, getAbstand, getHerkunft, setAbstand, setHerkunft, ... lässt sich auch der Algorithmus von Dijkstra implementieren. Du kannst dich an der Implementierung des Algorithmus von Moore orientieren. Zum Testen kannst du das folgende Testprogramm nutzen und variieren.

# Erzeugung des Testgraphen
testgraph_mit_gewichten = \
[
['A', [('C', 20), ('E', 2), ('G', 9)]],
['B', [('C', 1), ('D', 8)]],
['C', [('A', 20), ('D', 10), ('E', 13)]],
['D', [('B', 8), ('E', 16)]],
['E', [('D', 16), ('G', 5)]],
['F', [('B', 3), ('D', 4), ('H', 5)]],
['G', [('D', 2)]],
['H', [('F', 5), ('G', 7)]]
]

# Test des Dijkstra-Algorithmus
start = 'A'
ziel = 'B'
print('kürzester Weg von', start, 'nach', ziel, ':')
(weg, laenge) = kuerzesterWegDijkstra(testgraph_mit_gewichten, start, ziel)
for w in weg:
    print(w)
print('Weglänge:', laenge)

Aufgabe 4

Eine weitere Implementierung des Algorithmus von Dijkstra findest du in der Klasse GraphDijkstra (siehe graph_dijkstra.txt).

Objekte der Klasse GraphDijkstra stellen die Operation kuerzesterWegDijkstra zur Verfügung, mit der man Wege mit geringster Anzahl von Zwischenknoten in Graphen bestimmen kann.

Teste auch diese Implementierung des Algorithmus von Dijkstra. Das folgende Testprogramm verdeutlicht die Verwendung der Klasse GraphDijkstra am Demo-Graphen graph_mit_gewichten.xml.

from graph_dijkstra import *

# Erzeugung des Graph-Objekts
g = GraphDijkstra()
# Erzeugung der Knoten und Kanten aus einer GraphML-Datei
datei = open("graph_mit_gewichten.xml", "r")
xml_quelltext = datei.read()
g.graphmlToGraph(xml_quelltext) 
# Kontrollausgabe des Graphen
print('Graph:')
for knoten in g.getAlleKnoten():
    print(knoten, ':', g.getAlleNachbarn(knoten))
print()
# Test des Dijkstra-Algorithmus
start = 'A'
ziel = 'B'
print('kürzester Weg von', start, 'nach', ziel, ':')
(weg, laenge) = g.kuerzesterWegDijkstra(start, ziel)
for w in weg:
    print(w)
print('Weglänge:', laenge)