Trouvez l'itinéraire le plus court avec l'algorithme de Python Dijkstra

Problème d'itinéraire le plus court [méthode Dixtra](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).

(À propos de la méthode Dyxtra de Wikipedia)
Méthode Dyxtra (méthode Dyxtra, anglais: Dijkstra's) est en théorie des graphes
Il s'agit d'un algorithme basé sur la recherche de la meilleure priorité pour résoudre le problème du chemin le plus court au point de départ unique lorsque les pondérations latérales ne sont pas négatives.
Bellman si les poids latéraux contiennent des nombres négatifs-La méthode Ford, etc. peut être utilisée. Lorsque tous les poids latéraux ont le même nombre non négatif
La recherche de priorité de largeur est rapide et l'itinéraire le plus court peut être calculé en temps linéaire.
De plus, si le poids latéral est un entier positif dans un graphe non orienté, cela dépend de l'algorithme de Thorup.
Il est possible de calculer en temps linéaire, mais ce n'est pas très pratique.

La méthode Dyxtra recherche chaque nœud par ordre croissant de distance à partir du "Node 1" et recherche la distance la plus courte d'un nœud spécifique. En termes de réduction sensuelle des candidats, la méthode de limitation de branche utilisée dans Résoudre le problème du sac à dos Python avec la méthode de branche et de liaison J'avais un sentiment similaire.

Nous vous serions reconnaissants si vous pouviez nous faire savoir s'il y a des lacunes ou des suggestions d'amélioration concernant le code.

problème

Il existe les itinéraires suivants. Il y a 5 nœuds de 1 à 5, et le nombre sur l'itinéraire est le temps requis. Trouvez l'itinéraire le plus court entre «Node 1» et «Node 5».

répondre

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 des distances entre les nœuds initiaux

node_num = len(route_list) #Nombre de nœuds

unsearched_nodes = list(range(node_num)) #Nœud non recherché
distance = [math.inf] * node_num #Liste des distances par nœud
previous_nodes = [-1] * node_num #Liste des nœuds qui atteignent le nœud précédent par la route la plus courte
distance[0] = 0 #La distance initiale des nœuds est de 0

# @Ajout de la fonction du commentaire de GDaigo 2017/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): #Répétez jusqu'à ce qu'il n'y ait plus de nœuds non recherchés
    #Tout d'abord, sélectionnez le nœud non recherché avec la plus petite distance.
    posible_min_distance = math.inf #Distance temporaire pour trouver la plus petite distance. La valeur initiale est définie sur inf.
    for node_index in unsearched_nodes: #Boucle de nœuds inexplorés
        if posible_min_distance > distance[node_index]: 
            posible_min_distance = distance[node_index] #Mettre à jour si une valeur plus petite est trouvée
    target_min_index = get_target_min_index(posible_min_distance, distance, unsearched_nodes) #Obtenez le numéro d'index le plus bas parmi les nœuds non recherchés
    unsearched_nodes.remove(target_min_index) #Supprimé de la liste non recherchée car il sera recherché ici

    target_edge = route_list[target_min_index] #Liste des arêtes s'étendant à partir du nœud cible
    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 #Mettre à jour la distance si elle est inférieure à la distance précédemment définie
                previous_nodes[index] =  target_min_index #Également mis à jour la liste des nœuds arrivés immédiatement avant

#Voir les résultats ci-dessous

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("-----distance-----")
print(distance[node_num - 1])

résultat

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