Ali Buch in Python: Sec.2-5 Dyxtra-Methode

Die Dyxtra-Methode ist eine Lösung für das Problem, den Mindestabstand zwischen zwei Punkten in einem bestimmten gewichteten ungerichteten Graphen zu ermitteln. Sie ist in Ordnung, es sei denn, es gibt eine negativ gewichtete Kante.

Ich hatte Angst, als ich die Erklärung las, aber als ich über eine andere Implementierung nachdachte, die ein Diagramm wie unten gezeigt erstellt, verliebte ich mich in sie.

Zur Implementierung wurde der gewichteten Diagrammklasse die folgende Methode hinzugefügt. Als Operation

1. Entfernen Sie die Kante von from_node nach to_node
2. Wenn from_node in 1 schwebt, entfernen Sie from_node aus dem Diagramm

    def remove_wo_weight(self, from_node, to_node):

        if from_node in self:
            count = 0
            for [node, weight] in self[from_node]:
                if node == to_node:
                    self[from_node].pop(count)
                count += 1

            if self[from_node] == []:

                self.pop(from_node)

Der Code für die Dyxtra-Methode ist unten.

import mygraph

print("number of nodes")
N = int(input())

print("input graph")
graph = mygraph.WeightedGraph()

while 1:

    inputline = input()

    if inputline == "":
        break

    inputline = list(map(int, inputline.split()))

    graph.join(inputline[0], inputline[1], inputline[2])

graph = graph.undirected()


for node in graph:
    if not isinstance(graph[node][0], list):
        graph[node] = [graph[node]]

print("Start?")
startpos = int(input())
print("Goal?")
goalpos = int(input())


dp = N * [float("INF")]

minlength_graph = mygraph.WeightedGraph()

minlength_graph.join(startpos, startpos, 0)


while 1:

    shortest_comb = [0, 0, float("INF")]

    for min_node in minlength_graph:

        for [to_node, to_weight] in graph[min_node]:

            if shortest_comb[2] > minlength_graph.weight(startpos, min_node) + to_weight:

                shortest_comb = [min_node, to_node, minlength_graph.weight(
                    startpos, min_node) + to_weight]

    minlength_graph.join(startpos, shortest_comb[1], shortest_comb[2])

    for fixed_nodes in minlength_graph:

        graph.remove_wo_weight(fixed_nodes, shortest_comb[1])

        graph.remove_wo_weight(shortest_comb[1], fixed_nodes)

    if shortest_comb[1] == goalpos:

        print(shortest_comb[2])

        break

    minlength_graph = minlength_graph.undirected()

Eingabe und Ausgabe weggelassen (wie in Bellmanford)

Erstellen Sie ein Diagramm = minlength_graph, das die Punkte, an denen die Anfangsposition und der Abstand festgelegt sind, mit dem Abstand zu diesem Punkt als Gewicht verbindet, und löschen Sie die Kante zwischen den im minlength_graph enthaltenen Knoten mit graph.remove_wo_weight () aus dem ursprünglichen Diagramm. Ich werde gehen.

Kurz gesagt, minlength_graph fungiert nur als dp-Liste, aber ich habe das Gefühl, dass es visuell einfacher zu verstehen ist (?) (Im Folgenden gif).

Nachtrag) In Anbetracht des Rechenaufwands ist es besser, nicht nur den Knoten mit der kürzesten Entfernung aufzuzeichnen, sondern auch den Knoten, der dem zweiten am nächsten liegt. Dann müssen im nächsten Schritt nur der Abstand zum Punkt neben dem neu bestimmten Punkt und der Abstand zum zweitkürzesten Punkt im vorherigen Schritt verglichen werden, damit kein Abfall entsteht.