Objectif

Trouvez la distance la plus courte d'un sommet à un autre. (Point de départ unique et itinéraire le plus court) ** Peut être utilisé même s'il y a un côté avec un coût négatif **.

principe

Soit $ V $ le nombre de sommets et $ E $ le nombre de côtés du graphe. Créez une liste $ d $ qui enregistre le coût minimum pour chaque sommet. Ici, la distance à son propre point est fixée à 0, et la distance aux autres points est INF. De là, regardez tous les côtés et mettez à jour la distance la plus courte. Plus précisément, si le côté $ e $ a des informations qui coûtent $ cost $ du sommet $ de $ au sommet $ à , $d[from] + cost < d[to]$$ Quand, la valeur de $ d [to] $ est mise à jour à $ d [from] + cost $. Un total de $ V -1 $ fois pour regarder de tous les côtés déterminera tous les coûts minimaux en l'absence de fermetures négatives. En d'autres termes, si le coût minimum est toujours mis à jour au moment $ V $ ème, il aura une clôture négative, de sorte que le coût minimum correct ne peut pas être obtenu. Alors, pourquoi est-il correct de terminer l'opération dans une boucle $ V -1 $? Expliquez comment vous comprendre. Le même sommet ne sera jamais inclus dans le chemin le moins coûteux vers un sommet. S'il est inclus, il y a un itinéraire fermé négatif, donc l'itinéraire correct ne peut pas être trouvé en premier lieu. D'après ce qui précède, le nombre maximum de côtés inclus dans le chemin le plus court vers un certain sommet est $ V -1 $. Comme vous pouvez le voir en vérifiant le code après cela, l'ordre des côtés est l'ordre d'entrée. (Il n'est pas recherché dans l'ordre de proximité comme la recherche de priorité de largeur.) En d'autres termes, considérez le processus de recherche de l'itinéraire le plus court de $ V -1 $. Espérons qu'une boucle suivra les bords dans l'ordre à partir de l'avant, et cet itinéraire le plus court peut être trouvé. Cependant, supposons que l'ordre des côtés à examiner soit soigneusement arrangé à l'arrière. À ce stade, si le côté avant n'est pas examiné, le côté suivant ne peut pas être considéré comme faisant partie de l'itinéraire le plus court. (Parce que la distance à $ de $ n'est pas INF ou le coût minimum) En d'autres termes, dans ce cas, un seul des itinéraires les plus courts peut être trouvé pour chaque boucle. C'est donc le pire des cas et nécessite des boucles $ V -1 $.

Dans ce cas, je l'ai implémenté avec l'intention de rechercher dans l'ordre de proximité en termes de recherche de priorité de largeur, mais s'il y a un chemin fermé négatif, la valeur continuera à être mise à jour indéfiniment, donc j'ai senti qu'il était nécessaire de le concevoir. Quand ce n'était qu'un coût positif, je l'ai jeté dans le problème de Dyxtra d'Aizu Online et c'était la bonne réponse, alors je me demande si elle a aussi un nom.

Analyse de calcul

Dans le pire des cas, l'opération pour voir tous les côtés est effectuée $ V -1 $ fois, donc le montant du calcul est $ O (EV) $.

la mise en oeuvre

# O(EV)
def bellman_ford(s):
    d = [float('inf')]*n #Coût minimum pour chaque sommet
    d[s] = 0 #La distance à soi est 0
    for i in range(n):
        update = False #La mise à jour a-t-elle été effectuée?
        for x, y, z in g:
            if d[y] > d[x] + z:
                d[y] = d[x] + z
                update = True
        if not update:
            break
        #Il y a une route fermée négative
        if i == n - 1:
            return -1
    return d

n, w = [int(x) for x in input().split()] # n:Nombre de sommets, w:Nombre de côtés
g = []
for _ in range(w):
    x, y, z = [int(x) for x in input().split()] #point de départ,point final,Coût
    g.append([x, y, z])
    g.append([y, x, z]) #Supprimé dans le graphique dirigé
print(bellman_ford(0))

en conclusion

En ce qui concerne le code, cette fois je suis assez inquiet de la façon de penser, alors n'hésitez pas à le conseiller si vous le souhaitez!

Les références

Livre du défi du concours de programmation