Floyd-Warshall-Pfadrekonstruktion

Question

Nachfolgend finden Sie die Implementierung für den Floyd-Warshall-Algorithmus, bei dem alle Paare die kürzesten Pfade für einen bestimmten gewichteten Graphen finden.

Die Funktion verwendet floyd_warshallein Diagramm als Eingabe, das durch eine Kantenliste in Form von [ Quelle , Ziel , Gewicht ] dargestellt wird.

Die path_reconstructionFunktion gibt die kürzesten Pfade von jedem Scheitelpunkt aus, der mit jedem anderen Scheitelpunkt verbunden ist.

Bitte geben Sie Vorschläge für Verbesserungen jeglicher Art.

import sys

INF = sys.maxsize

def floyd_warshall(graph):
    source_vertices = [column[0] for column in graph]
    destination_vertices = [column[1] for column in graph]
    vertices = list(set(source_vertices) | set(destination_vertices))

    distance = [[INF] * len(vertices) for i in range(len(vertices))]
    next_vertices  = [[0]   * len(vertices) for i in range(len(vertices))]

    for i in range(len(vertices)):
        distance[i][i] = 0
    for source, destination, weight in graph:
        distance[source-1][destination-1] = weight
        next_vertices[source-1][destination-1] = destination-1

    for k in range(len(vertices)):
        for i in range(len(vertices)):
            for j in range(len(vertices)):
                if distance[i][j] > distance[i][k] + distance[k][j]:
                    distance[i][j] = distance[i][k] + distance[k][j]
                    next_vertices[i][j]  = next_vertices[i][k]

    path_reconstruction(distance, next_vertices)

def path_reconstruction(dist, nxt):
    print("Edge \t\t Distance \t Shortest Path")
    for i in range(len(dist)):
        for j in range(len(dist)):
            if i != j:
                path = [i]
                while path[-1] != j:
                    path.append(nxt[path[-1]][j])
                print("(%d, %d) \t\t %2d \t\t %s"
                      % (i + 1, j + 1, dist[i][j], ' - '.join(str(p + 1) for p in path)))
    print()

def main():
    edge_list1 = [
        [1, 3, -2],
        [2, 1, 4],
        [2, 3, 3],
        [3, 4, 2],
        [4, 2, -1]
    ]
    edge_list2 = [
        [1, 2, 10],
        [1, 3, 20],
        [1, 4, 30],
        [2, 6, 7],
        [3, 6, 5],
        [4, 5, 10],
        [5, 1, 2],
        [5, 6, 4],
        [6, 2, 5],
        [6, 3, 7],
        [6, 5, 6]
    ]

    floyd_warshall(edge_list1)
    floyd_warshall(edge_list2)

if __name__ == '__main__':
    main()

Answer 1

FMc hat einige hervorragende Punkte gemacht. Ich werde versuchen, diese nicht zu wiederholen.

Eckpunkte

Sie bestimmen die Liste der Eckpunkte mit:

    source_vertices = [column[0] for column in graph]
    destination_vertices = [column[1] for column in graph]
    vertices = list(set(source_vertices) | set(destination_vertices))

und verwenden Sie dann wiederholt len(vertices)Ihren gesamten Code.

FMc schlägt vor, Folgendes zu verwenden:

    vertices = set(col[i] for col in graph for i in (0, 1))
    n = len(vertices)

Beide Implementierungen verwenden Mengen, um eine Abdeckung aller Scheitelpunkte zu bilden. Das macht aber eigentlich keinen Sinn. Sie verwenden range(len(vertices)), um die Indizes zu bestimmen. Was wäre, wenn die Diagramme die Eckpunkte 1, 2, 4 und 5 verwenden würden? Ihre Sets wäre {1, 2, 4, 5}, die Länge des Satzes ist 4, und range(4)erzeugt die Indizes 0, 1, 2, und 3. Aber Sie führen aus:

    for source, destination, weight in graph:
        distance[source-1][destination-1] = weight

Sie würden finden sourceoder destinationist 5, berechnen Sie subtrahieren Sie 1, um den Index 4 zu erhalten, und stellen Sie fest, dass Sie vom Ende der Matrix gefallen sind!

Es ist klar, dass alle Indizes von 1bis Nverwendet werden müssen, ohne dass Lücken zulässig sind. Aber dann brauchst du kein Set. Sie müssen nur den maximalen Index finden.

    n = max(edge[col] for edge in graph for col in (0, 1))

Die Indizierung ist langsam

Wie oft wird in diesem Code für 100 Eckpunkte distance[i]ausgewertet? Wie wäre es distance[k]?

    for k in range(len(vertices)):
        for i in range(len(vertices)):
            for j in range(len(vertices)):
                if distance[i][j] > distance[i][k] + distance[k][j]:
                    distance[i][j] = distance[i][k] + distance[k][j]
                    next_vertices[i][j]  = next_vertices[i][k]

distance[i]wird irgendwo zwischen 2000000 und 4000000 mal nachgeschlagen? Scheint vielleicht übertrieben? distance[k]wird zwischen 1000000 und 2000000 mal nachgeschlagen. Ein bisschen weniger, aber immer noch einige.

Sobald Sie eingegeben haben, ist die erste forSchleife keine Konstante für diese Iteration. Sie könnten distance[k]einmal nachschlagen . Sobald Sie die zweite forSchleife betreten haben , iist dies ebenfalls eine Konstante für diese Iteration. Sie könnten distance[i]einmal nachschlagen .

    for k in range(len(vertices)):
        distance_k = distance[k]
        for i in range(len(vertices)):
            distance_i = distance[i]
            for j in range(len(vertices)):
                if distance_i[j] > distance_i[k] + distance_k[j]:
                    distance_i[j] = distance_i[k] + distance_k[j]
                    next_vertices[i][j]  = next_vertices[i][k]

Jetzt haben wir die Entfernung [k] nur 100 Mal und die Entfernung [i] nur 10000 Mal nachgeschlagen. Dies wird eine Geschwindigkeitsverbesserung sein.

Wir können die for-Schleifen besser machen: die Indizes abrufen und die Werte zusammen enumeratenachschlagen, die Zeilen der distanceMatrix verwenden und durchlaufen :

    for k, distance_k in enumerate(distance):
        for i, distance_i in enumerate(distance):
            for j in range(len(vertices)):
                if distance_i[j] > distance_i[k] + distance_k[j]:
                    distance_i[j] = distance_i[k] + distance_k[j]
                    next_vertices[i][j]  = next_vertices[i][k]

Auch hier distance_i[k]ändert sich nicht in der inneren Schleife, so dass wir es einmal in der mittleren Schleife nachschlagen können:

    for k, distance_k in enumerate(distance):
        for i, distance_i in enumerate(distance):
            dist_ik = distance_i[k]
            for j in range(len(vertices)):
                dist_ik_kj = dist_ik + distance_k[j]
                if distance_i[j] > dist_ik_kj:
                    distance_i[j] = dist_ik_kj 
                    next_vertices[i][j]  = next_vertices[i][k]

Schließlich können wir die distance_kZeile der Matrix durchlaufen , um zusätzliche Suchkosten zu vermeiden:

    for k, distance_k in enumerate(distance):
        for i, distance_i in enumerate(distance):
            dist_ik = distance_i[k]
            for j, dist_kj in enumerate(distance_k):
                dist_ik_kj = dist_ik + dist_kj
                if distance_i[j] > dist_ik_kj:
                    distance_i[j] = dist_ik_kj 
                    next_vertices[i][j]  = next_vertices[i][k]

Beide next_vertices[i]und next_vertices[i][k]sind in der inneren Schleife konstant; Wir könnten sie einmal in der mittleren Schleife nachschlagen, um zusätzliche Einsparungen zu erzielen. Sie könnten sogar zip distanceund next_verticeszusammen in der for i, ...Aussage und beide distance_iund next_vertices_igleichzeitig nachschlagen . Aber vielleicht wird das etwas zu weit fortgeschritten.

Erinnerung

Python-Listen sind Speicherfresser. Dies spielt keine Rolle, wenn Ihre Diagramme nicht mehr als ein paar hundert Eckpunkte haben. Wenn Sie jedoch größere Diagramme unterstützen möchten (Tausende von Scheitelpunkten? Hunderttausende von Scheitelpunkten?), Sollten Sie speichereffiziente Strukturen verwenden.

Sie können verwenden numpy, um Ihre NxN distanceund next_verticesMatrizen zu erstellen . Aber wenn Sie nicht numpyinstalliert haben, müssen wir diesen Vorschlaghammer nicht verwenden. Python wird mit speichereffizienteren arrayObjekten geliefert, die nur skalare Informationen (Ganzzahlen, Gleitkommazahlen, Zeichen) anstelle der heterogenen Jack-of-all-Trade-Listen von Listen speichern können.

next_verticesHalten Sie ganzzahlige Scheitelpunktwerte. Anstatt von:

next_vertices  = [[0]   * len(vertices) for i in range(len(vertices))]

Erwägen:

zeros = [0] * len(vertices)
next_vertices = [array.array('I', zeros) for _ in range(len(vertices))]

Der Rest des Codes müsste nicht geändert werden. Sie greifen weiterhin auf die Daten wie zu next_vertices[i][j].

Dies erzeugt eine listder arrayganzen Zahlen, wobei die Anordnung ein nur 2 Bytes pro Wert annimmt, anstelle von 8 Byte pro Element sowie der Speicherbedarf jeder ganzen Zahl (etwa 28 Bytes je).

Sie können etwas Ähnliches für die distanceMatrix tun . Aber jetzt müssen wir wissen: Sind die Gewichte immer ganzzahlige Werte oder sind sie Gleitkommawerte? Möglicherweise möchten Sie den 'd'Typcode verwenden, wenn die Gewichte gebrochen sein können. Einzelheiten finden Sie im Array .

Answer 2

Ihr Programm bietet ein gutes Beispiel dafür, wie Sie die Lesbarkeit von Code durch einige gängige Techniken verbessern können: (1) Convenience-Variablen, um ausführliche Wiederholungen zu vermeiden; (2) Code, der als kleine kommentierte "Absätze" oder Blöcke organisiert ist; und (3) die Verwendung kürzerer Variablennamen, um das visuelle Gewicht des Codes zu verringern, wodurch die Lesefreundlichkeit und das visuelle Scannen verbessert werden. Beachten Sie, dass Kurznamen mit Bedacht verwendet werden müssen: Da sie kryptisch sein können, leiten kurze Variablen ihre Bedeutung normalerweise entweder aus einer konsistent verwendeten Konvention im Programm oder aus anderen kontextbezogenen Hinweisen ab (z. B. aus nahegelegenen Funktionen oder Sammlungen mit expliziteren Namen und aus gut platzierte Kommentare). Hier ist eine stark bearbeitete Version vonfloyd_warshall()in diese Richtung. Da ich faul bin, gehe ich davon aus, dass Sie Floyd-Warshall korrekt implementiert haben.

def floyd_warshall(graph):
    # Collect all vertices.
    vertices = set(
        col[i]
        for col in graph
        for i in (0, 1)
    )
    n = len(vertices)
    rng = range(n)

    # Initialize the distance and next-vertex matrix.
    dists = [
        [0 if i == j else INF for j in rng]
        for i in rng
    ]
    next_vertices = [
        [0 for j in rng]
        for i in rng
    ]

    # Populate the matrixes.
    for src, dst, weight in graph:
        i = src - 1
        j = dst - 1
        dists[i][j] = weight
        next_vertices[i][j] = j

    # Do that Floyd-Warshall thing.
    for k in rng:
        for i in rng:
            for j in rng:
                ikj = dists[i][k] + dists[k][j]
                if dists[i][j] > ikj:
                    dists[i][j] = ikj
                    next_vertices[i][j]  = next_vertices[i][k]

    return path_reconstruction(dists, next_vertices)

Ein größeres Problem ist, dass Ihre floyd_warshall()Funktion keine druckende Funktion aufrufen sollte. Vielmehr sollte es eine Art aussagekräftiger Daten zurückgeben. Dieser Ansatz macht Ihre Funktion leichter testbar. Könnte beispielsweise path_reconstruction()eine Liste deklarativer Diktate zurückgeben.

def path_reconstruction(dists, next_vertices):
    # Same ideas here: return data, don't print; use convenience
    # vars where they help with readability.
    rng = range(len(dists))
    paths = []
    for i in rng:
        for j in rng:
            if i != j:
                path = [i]
                while path[-1] != j:
                    path.append(next_vertices[path[-1]][j])
                paths.append(dict(
                    i = i,
                    j = j,
                    dist = dists[i][j],
                    path = path,
                ))
    return paths

Drucken Sie dann außerhalb des algorithmischen Codes.

def main():
    edge_lists = [
        [
            [1, 3, -2],
            [2, 1, 4],
            [2, 3, 3],
            [3, 4, 2],
            [4, 2, -1],
        ],
        [
            [1, 2, 10],
            [1, 3, 20],
            [1, 4, 30],
            [2, 6, 7],
            [3, 6, 5],
            [4, 5, 10],
            [5, 1, 2],
            [5, 6, 4],
            [6, 2, 5],
            [6, 3, 7],
            [6, 5, 6],
        ],
    ]
    for el in edge_lists:
        paths = floyd_warshall(el)
        for p in paths:
            print(p)