Problem mit Dijkstra-Algorithmus

[hoppelchen]

N'Abend,

ich habe ein kleines Problemchen mit der Implementierung des Dijkstra-Algos: Code wird problemlos ausgeführt, liefert aber nicht wie gewünscht die minimale Entfernung zwischen je zwei Punkten. Wäre super, wenn jemand von euch einen kleinen Blick darauf werfen könnte. Sehe den Wald vor lauter Bäumen nicht

Code: Alles auswählen

from numpy import *
Cols = 7 # Groesse der Matrix (Entfernungsmatrix)
infty = 10000
Distanz = zeros((Cols,1))
Vorgaenger = zeros((Cols,1))


def Dijkstra(Matrix, start):
  markiert = zeros((Cols,1))
  for i in range(0,Cols):
    Distanz[i] = infty
  for i in range(0,Cols):
    Vorgaenger[i] = -1
  Distanz[start] = 0
 
  Knoten = start
  marker = 0
  while marker == 0:
    minimum = infty
    for j in range (0,Cols):
      if markiert[j] == 0:
        if Distanz[j] < minimum:
          minimum = Distanz[j]
          Knoten = j
    for j in range (0,Cols):
      if markiert[j] == 0:  
        if Distanz[Knoten] + Matrix[Knoten][j] < Distanz[j]:
          Distanz[j] = Distanz[Knoten] + Matrix[Knoten][j]
          Vorgaenger[j] = Knoten
      markiert[Knoten] = 1
      marker = 0
    for j in range(0,Cols):
      if marker == 0:
        if markiert[j] == 1:
          marker = 1 
        else:
          marker = 0
  return Vorgaenger

Danke schonmal für eure Hilfe

[BlackJack]

@hoppelchen: Warum werden `Distanz` und `Vorgaenger` ausserhalb der Funktion definiert? Die gehören doch eindeutig dort hinein. Warum sind das Arrays in der Form? Hätten es nicht auch eindimensionale Arrays getan? Oder gar einfach nur Listen? Man könnte auch passendere Typen verwenden. `markiert` enthält Wahrheitswerte -- Python kennt `True` und `False`. Da braucht man also nicht 0 und 1 für missbrauchen. `Vorgaenger` enthält ja anscheinend die Knotennummer von den jeweiligen Vorgängerknoten. -1 ist ein gültiger Index für Listen oder `numpy.array`\s -- ist also kein so guter Platzhalter für "kein Wert". Eine Liste die Zahlen und `None` für "kein Wert" enthält, wäre besser.

Warum definierst Du Dein eigenes `infty` was dazu gar nicht unendlich ist? Du verdeckst mit der Definition das `infty`, welches Du aus `numpy` mit dem Sternchen-Import geholt hast. Sternchen-Importe sind übrigens in Programmen nicht gern gesehen, weil man sich da potentiell Unmengen von Namen in den Modulnamensraum holt. Bei `numpy` sind das mal eben über 500 Stück.

Warum definierst Du `Cols` fest? Man kann die Anzahl doch von `Matrix` abfragen -- dann funktioniert die Funktion mit beliebigen Adjazenzmatrizen.

Kann es passieren, dass in der ersten ``for``-Schleife innerhalb der ``while``-Schleife die Bedingung nie wahr wird und weder `Knoten` noch `minimum` neu gebunden werden? Was würde in so einem Fall mit dem Algorithmus passieren?

Könnte man statt `markiert` nicht einfach eine Menge von noch nicht besuchten Knoten in einem `set()` halten? Das könnte den Quelltext vielleicht etwas einfacher machen.

Sollen die beiden Zuweisungen am Ende der zweiten ``for``-Schleife in der ``while``-Schleife tatsächlich *dort* stehen? Die werden für jeden Schleifendurchlauf mit den selben Werten ausgeführt.

Und in Python solltest Du wenn es geht ohne unnötige Indexzugriffe auskommen. Man kann über Elemente von Listen direkt iterieren. Wenn man den Index nicht benötigt, wie bei der letzten ``for``-Schleife zum Beispiel. Die ist sowieso unnötig kompliziert. Statt dem ersten ``if`` hätte man vor der Schleife `marker` auf 0 setzen können -- äh ist es ja eh schon. Und dann bei einem Treffer einfach ``marker = 1`` und dann mit ``break`` die Schleife verlassen. Oder die ganzen 6 Zeilen einfach durch ``marker = any(markiert)`` ersetzen.

Nachtrag: Die konventionelle Einrückungstiefe bei Python betrrägt vier Leerzeichen pro Ebene. Und für die Gross-/Kleinschreibung bei Namen hat PEP 8 -- Style Guide for Python Code auch Empfehlungen. Zumal einige Namen IMHO aussagekräftiger gewählt werden können um ihren Inhalt besser zu beschreiben. `Matrix` ist ja zum Beispiel eine `adjazenzmatrix`. Und Namen hinter denen ein Containerobjekt steht, sollten nicht in Einzahl benannt werden. `Distanz` steht ja zum Beispiel nicht für *einen* Wert sondern für mehrere `distanzen`.

Ich habe das mal geändert und aus den Numpy-Arrays normale Listen gemacht, deren Länge sich aus der übergebenen Matrix bestimmt (ungetestet):

Code: Alles auswählen

import numpy as np


def dijkstra(adjazenzmatrix, start):
    node_count = len(adjazenzmatrix)
    distanzen = [np.infty] * node_count
    vorgaenger = [None] * node_count
    markiert = [False] * node_count
    distanzen[start] = 0
    knoten = start
    marker = False
    while not marker:
        minimum = np.infty
        for j in xrange(node_count):
            if markiert[j] == 0:
                if distanzen[j] < minimum:
                    minimum = distanzen[j]
                    knoten = j
        for j in xrange(node_count):
            if markiert[j] == 0:
                neue_distanz = distanzen[knoten] + adjazenzmatrix[knoten][j]
                if  neue_distanz < distanzen[j]:
                    distanzen[j] = neue_distanz
                    vorgaenger[j] = knoten
            # 
            # FIXME Sind die folgenden zwei Zeilen korrekt?
            # 
            markiert[knoten] = True
            marker = False
        marker = any(markiert)
    return vorgaenger

Jetzt schau Dir da doch noch mal die Abbruchbedingung der ``while``-Schleife an -- die scheint mir nicht korrekt zu sein. Man käme hier ohne `marker` aus wenn man den Ausdruck direkt als Bedingung in die ``while``-Schleife schreibt und dann ist es IMHO sehr offensichtlich falsch.

Ansonsten könntest Du auch mal eine Beispielmatrix zeigen und was da heraus kommt. Und was Du stattdessen erwartest.

[hoppelchen]

Hi,

erstmal vielen lieben dank für deine nützlichen Hinweise.
Habe den Code mal mit folgender Matrix durchlaufen lassen:

Beispielmatrix (aus externer Datei Matrix.dat):
0 3 5 3 2 4 3
3 0 4 6 3 5 1
5 4 0 9 3 2 5
2 5 9 0 4 4 5
2 3 3 3 0 3 2
5 4 2 4 3 0 5
2 1 5 5 3 5 0

Code: Alles auswählen

adjazenzmatrix = np.genfromtxt("Matrix.dat")
print dijkstra(adjazenzmatrix, 2)

liefert mir aber

Code: Alles auswählen

[2, 2, None, 2, 2, 2, 2]

, was offensichtlich nicht stimmen kann! - soweit war mein Code auch schon

Bin immer noch am grübeln und für Geistesblitze offen

[BlackJack]

Wenn das offensichtlich nicht stimmen kann, dann verrate doch mal das richtige Ergebnis oder sag warum das nicht stimmt. Ich habe gerade mal versucht das aufzumalen, aber bei dem Graphen ist ja jeder Knoten mit jedem verbunden und es gibt gerichtete Kanten in beide Richtungen, teilweise mit unterschiedlicher Gewichtung, das ist einfach nur unübersichtlich.

Obwohl ich auch ein anderes Ergebnis heraus habe: [2, 2, None, 5, 2, 2, 2]. Also bei einem Knoten scheint ein kleiner Umweg günstiger zu sein, als die direkte Verbindung. Der Code dazu sieht so aus:

Code: Alles auswählen

INFINITY = float('inf')

GRAPH_SOURCE = """\
0 3 5 3 2 4 3
3 0 4 6 3 5 1
5 4 0 9 3 2 5
2 5 9 0 4 4 5
2 3 3 3 0 3 2
5 4 2 4 3 0 5
2 1 5 5 3 5 0
""".splitlines()


def dijkstra(adjazenzmatrix, start):
    node_count = len(adjazenzmatrix)
    distanzen = [INFINITY] * node_count
    vorgaenger = [None] * node_count
    unbesuchte_knoten = set(xrange(node_count))
    distanzen[start] = 0
    knoten = start
    while unbesuchte_knoten:
        knoten = min(unbesuchte_knoten, key=distanzen.__getitem__)
        for j in unbesuchte_knoten:
            neue_distanz = distanzen[knoten] + adjazenzmatrix[knoten][j]
            if  neue_distanz < distanzen[j]:
                distanzen[j] = neue_distanz
                vorgaenger[j] = knoten
        unbesuchte_knoten.remove(knoten)
    return vorgaenger


def main():
    adjazenzmatrix = [map(int, line.split()) for line in GRAPH_SOURCE]
    print dijkstra(adjazenzmatrix, 2)

if __name__ == '__main__':
    main()

[hoppelchen]

Wenn das offensichtlich nicht stimmen kann, dann verrate doch mal das richtige Ergebnis oder sag warum das nicht stimmt. Ich habe gerade mal versucht das aufzumalen, aber bei dem Graphen ist ja jeder Knoten mit jedem verbunden und es gibt gerichtete Kanten in beide Richtungen, teilweise mit unterschiedlicher Gewichtung, das ist einfach nur unübersichtlich.

Kann eben aus dem Grund nicht stimmen, den du auch angeführt hast: Knoten 4 ist besser erreichbar als über den "Startknoten". Das Beispiel aufzumalen ist etwas kritisch, da geb ich dir recht, dewegen wollte ich den Algo implementieren Am Rande: das Beispiel hab ich mir nur zu Testzwecken aus den Fingern gesaugt (Demnach hab ich dafür auch keine Lösung ). Mir gehts bei der ganzen Sache ums herantasten an Python, da ich mich (unter anderem) etwas mit Graphentheorie beschäftige und python mit numpy mir hierzu als vernünftig erscheint

Jetzt hast du da ne tolle Implementierung des Algos "geliefert". Ich verbring dann mal die heutige Nacht damit, weiterhin den Fehler in meinem Code zu suchen und deine Implementierung zu verstehen *Kaffe hol'*

Vielen lieben Dank für deine Hilfe

[BlackJack]

@hoppelchen: Eigentlich habe ich ja nur Deinen schrittweise von `numpy` "befreit" und kompakter geschrieben. Der sollte sich nur durch die Abbruchbedingung von Deinem ursprünglichen unterscheiden.