Algorithmensammlung: Graphentheorie: Dijkstra-Algorithmus

Algorithmensammlung: Graphentheorie

• Algorithmus von Kruskal
• Algorithmus von Prim
• Breitensuche (BFS - breadth first search)
• Dijkstra-Algorithmus
• Tiefensuche (DFS - depth first search)

Dijkstra-Algorithmus

Der Dijkstra-Algorithmus bestimmt in einem gerichteten Graphen mit gewichteten Kanten den kürzesten (= kosteneffizientesten) Weg zwischen zwei angegebenen Knoten. Bekanntestes Beispiel für seine Anwendung sind Routenplaner.

Für weitere Beispiele und eine informelle Beschreibung siehe Dijkstra-Algorithmus.

Python

def dijkstra(knoten, kanten, start, ziel):
    # knoten ist eine Liste von Knoten
    # kanten ist eine Liste von 3-Tupeln:
    #   (knoten1, knoten2, kosten)
    # start ist der Knoten, in dem die Suche startet
    # ziel ist der Knoten, zu dem ein Weg gesucht werden soll
    # Gibt ein Tupel zurück mit dem Weg und den Kosten 
    #
    knotenEigenschaten = [ [i, "inf", None, False] for i in knoten if i != start ]
    knotenEigenschaten += [ [start, 0, None, False] ]
    for i in range(len(knotenEigenschaten)):
        knotenEigenschaten[i] += [ i ]
 
    while True:
        unbesuchteKnoten = filter(lambda x: not x[3], knotenEigenschaten)
        if not unbesuchteKnoten: break
        sortierteListe = sorted(unbesuchteKnoten, key=lambda i: i[1])
        aktiverKnoten = sortierteListe[0]
        knotenEigenschaten[aktiverKnoten[4]][3] = True
        if aktiverKnoten[0] == ziel:
                break
        aktiveKanten = filter(lambda x: x[0] == aktiverKnoten[0], kanten)
        for kante in aktiveKanten:
                andererKnotenId = filter(lambda x: x[0] == kante[1], knotenEigenschaten)[0][4]
                gewichtSumme = aktiverKnoten[1] + kante[2]
                if gewichtSumme < knotenEigenschaten[andererKnotenId][1]:
                        knotenEigenschaten[andererKnotenId][1] = gewichtSumme
                        knotenEigenschaten[andererKnotenId][2] = aktiverKnoten[4]
 
    if aktiverKnoten[0] == ziel:
        weg = []
        weg += [ aktiverKnoten[0] ]
        kosten = 0
        while aktiverKnoten[0] != start:
                aktiverKnoten = knotenEigenschaten[aktiverKnoten[2]]
                weg += [ aktiverKnoten[0] ]
                kosten += aktiverKnoten[1]
        weg.reverse()
        return (weg, kosten)
    else:
        raise "Kein Weg gefunden"