Livre Ali en python: méthode Dyxtra Sec.2-5

La méthode Dyxtra est une solution au problème de trouver la distance minimale entre deux points sur un graphe non orienté pondéré donné, et est correcte sauf s'il y a un bord pondéré négatif.

J'avais peur en lisant l'explication, mais après avoir pensé à une autre implémentation qui crée un graphique comme indiqué ci-dessous, j'en suis tombée amoureuse.

Pour l'implémentation, la méthode suivante a été ajoutée à la classe de graphes pondérés. En tant qu'opération

1. Supprimez l'arête de from_node à to_node
2. Si from_node flotte à 1, supprimez from_node du graphique

    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)

Le code de la méthode Dyxtra est ci-dessous.

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()

Entrée et sortie omises (comme à Bellmanford)

Créez un graphe = minlength_graph qui relie les points où la position initiale et la distance sont fixées avec la distance à ce point comme poids, et supprimez l'arête entre les nœuds inclus dans le minlength_graph du graphe d'origine avec graph.remove_wo_weight (). J'irai.

En bref, cela fait juste que minlength_graph agisse comme une liste de dp, mais j'ai l'impression que c'est devenu plus facile à comprendre visuellement (?) (Ci-après gif).

Postscript) Compte tenu de la quantité de calcul, il est préférable d'enregistrer non seulement le nœud avec la distance la plus courte mais également le nœud le plus proche du second. Ensuite, à l'étape suivante, seule la distance au point adjacent au point nouvellement déterminé et la distance au deuxième point le plus court de l'étape précédente doivent être comparées, de sorte qu'il n'y ait pas de gaspillage.