@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.