Finden Sie den kürzesten Weg mit dem Python Dijkstra-Algorithmus

Problem mit der kürzesten Route [Dixtra-Methode](https://ja.wikipedia.org/wiki/%E3%83%80%E3%82%A4%E3%82%AF%E3%82%B9%E3%83% 88% E3% 83% A9% E6% B3% 95).

(Über die Dyxtra-Methode aus Wikipedia)
Dyxtra-Methode (Dyxtra-Methode, Englisch: Dijkstra's Algorithmus) ist in der Graphentheorie
Dies ist ein Algorithmus, der auf der Suche mit der besten Priorität zur Lösung des Problems des kürzesten Wegs eines einzelnen Startpunkts basiert, wenn die Seitengewichte nicht negativ sind.
Bellman, wenn die Seitengewichte negative Zahlen enthalten-Ford-Methode usw. kann verwendet werden. Wenn alle Seitengewichte die gleiche nicht negative Zahl haben
Die Suche nach der Breitenpriorität ist schnell und die kürzeste Route kann in linearer Zeit berechnet werden.
Wenn das Seitengewicht in einem ungerichteten Diagramm eine positive Ganzzahl ist, hängt dies vom Thorup-Algorithmus ab.
Es ist möglich, in linearer Zeit zu berechnen, aber es ist nicht sehr praktisch.

Die Dyxtra-Methode durchsucht jeden Knoten in aufsteigender Reihenfolge der Entfernung von "Knoten 1" und sucht nach der kürzesten Entfernung eines bestimmten Knotens. In Bezug auf die sinnliche Eingrenzung der Kandidaten die in [Lösen des Python-Rucksackproblems mit der Verzweigungs- und gebundenen Methode] verwendete Verzweigungsbegrenzungsmethode (http://qiita.com/shizuma/items/b0752fd4cd39583d7e54) Ich hatte ein ähnliches Gefühl.

Wir würden uns freuen, wenn Sie uns mitteilen könnten, ob es Mängel oder Verbesserungsvorschläge bezüglich des Codes gibt.

Problem

Es gibt folgende Routen. Es gibt 5 Knoten von 1 bis 5, und die Nummer auf der Route ist die erforderliche Zeit. Finden Sie den kürzesten Weg von "Knoten 1" zu "Knoten 5".

Antworten

import math

route_list = [[0, 50, 80, 0, 0], [0, 0, 20, 15, 0 ], [0, 0, 0, 10, 15], [0, 0, 0, 0, 30], [0, 0, 0, 0, 0]] #Liste der Abstände zwischen Anfangsknoten

node_num = len(route_list) #Anzahl der Knoten

unsearched_nodes = list(range(node_num)) #Unerforschter Knoten
distance = [math.inf] * node_num #Liste der Entfernungen pro Knoten
previous_nodes = [-1] * node_num #Eine Liste der Knoten, die unmittelbar vor diesem Knoten auf der kürzesten Route eintreffen
distance[0] = 0 #Der anfängliche Knotenabstand beträgt 0

# @Funktion aus GDaigos Kommentar 2017 hinzugefügt/03/18
def get_target_min_index(min_index, distance, unsearched_nodes):
    start = 0
    while True:
        index = distance.index(min_index, start)
        found = index in unsearched_nodes
        if found:
            return index
        else:
            start = index + 1

while(len(unsearched_nodes) != 0): #Wiederholen, bis keine nicht durchsuchten Knoten mehr vorhanden sind
    #Wählen Sie zunächst den nicht durchsuchten Knoten mit dem geringsten Abstand aus.
    posible_min_distance = math.inf #Temporäre Entfernung, um die kleinste Entfernung zu finden. Der Anfangswert wird auf inf gesetzt.
    for node_index in unsearched_nodes: #Schleife von unerforschten Knoten
        if posible_min_distance > distance[node_index]: 
            posible_min_distance = distance[node_index] #Aktualisieren, wenn ein kleinerer Wert gefunden wird
    target_min_index = get_target_min_index(posible_min_distance, distance, unsearched_nodes) #Ermitteln Sie die niedrigste Indexnummer unter den nicht durchsuchten Knoten
    unsearched_nodes.remove(target_min_index) #Aus der nicht durchsuchten Liste entfernt, da hier gesucht wird

    target_edge = route_list[target_min_index] #Liste der Kanten, die sich vom Zielknoten erstrecken
    for index, route_dis in enumerate(target_edge):
        if route_dis != 0:
            if distance[index] > (distance[ target_min_index] + route_dis):
                distance[index] = distance[ target_min_index] + route_dis #Aktualisieren Sie die Entfernung, wenn sie geringer als die zuvor eingestellte Entfernung ist
                previous_nodes[index] =  target_min_index #Außerdem wurde die Liste der Knoten aktualisiert, die unmittelbar zuvor angekommen sind

#Ergebnisse unten anzeigen

print("-----Route-----")
previous_node = node_num - 1
while previous_node != -1:
    if previous_node !=0:
        print(str(previous_node + 1) + " <- ", end='')
    else:
        print(str(previous_node + 1))
    previous_node = previous_nodes[previous_node]

print("-----Entfernung-----")
print(distance[node_num - 1])

Ergebnis

-----Route-----
5 <- 3 <- 2 <- 1
-----Entfernung-----
85