Compréhension complète des concepts de Bellmanford et Dyxtra

Aperçu

Nous avons présenté la méthode dijkstra et la méthode bellman-ford lors d'une session d'étude interne. À cette époque, je recherchais diverses preuves de l'algorithme, mais j'ai remarqué qu'il n'y avait pas beaucoup d'articles expliqués. Personnellement, je pense que la question «Pourquoi cela se produit-il?» Est un facteur important, je voudrais donc présenter ces algorithmes en gardant cela à l'esprit.

Quel genre de personne est l'écrivain?

Historique de programmation: 1 an (Python uniquement) Thé Atcoder Je travaille pour une société de consignation d'analyse de données depuis avril 2020, mais pour une raison quelconque, j'étudie simplement les algorithmes.

Quand utilisez-vous cet algorithme?

Il est utilisé pour résoudre le problème de chemin le plus court du point de départ unique d'un graphe pondéré.

Pour chaque terme, Pondéré: coût nécessaire pour passer par le côté Point de départ unique: un point de départ Itinéraire le plus court: l'itinéraire du point de départ à la destination au moindre coût est.

Prenant le graphique ci-dessous comme exemple Le but est de trouver l'itinéraire le plus court à partir du point de départ $ A $ vers tous les côtés. À propos, l'itinéraire le plus court de $ A à E $ est （A→D→B→F→E） est. Nous trouverons cela à l'aide d'un algorithme.

Avant l'algorithme, les propriétés importantes du graphe

1. La route partielle la plus courte est la route la plus courte

La route partielle de la route la plus courte est la route la plus courte partout.

Preuve
Temporairement, dans le graphique ci-dessus, l'itinéraire le plus court de $ A à E $ （A→B→C→D→E　cost:5） ça ira.

Parmi ceux-ci, $ (A → B → C coût: 3) $ Est une route partielle de cette route la plus courte, mais si vous utilisez le sommet B'pour cette section Vous pouvez déplacer le coût de un de moins. Ensuite, l'itinéraire le plus court de cette section est （A→B'→C　cost:2） Par conséquent, $ A → E $ （A→B'→C→D→E　cost:4） Il peut être déplacé avec, ce qui contredit l'hypothèse. La route partielle de la route la plus courte est toujours la route la plus courte.

2. Détente du chemin

Si vous trouvez le chemin le plus court dans l'ordre à partir du sommet lié au point de départ, vous trouverez enfin tous les chemins les plus courts. En effet, après tout, le chemin le plus court obtenu progressivement à partir du point de départ devient un chemin partiel du sommet qui dépasse ce point.

Qu'est-ce que la méthode Bellmanford?

Trouvez le chemin le plus court entre tous les sommets. La principale différence avec la méthode Dyxtra est que ** les poids négatifs sont autorisés **.

Le processus de recherche de l'itinéraire le plus court est

1. Concentrez-vous sur tous les côtés et mettez à jour la valeur ** si vous pouvez réduire le coût des sommets qui passent par ces côtés **
2. Effectuez le processus de 1. ** (nombre de sommets-1) fois ** est.

Dans la figure ci-dessous,

À l'étape 1, vous pouvez commencer $ A $ et atteindre $ C $ au coût de 5 $, alors notez-le comme $ C: 5 $. Ensuite, $ A → B $ peut être atteint à $ -1 $, donc $ B: -1 $ et $ B → C $ peuvent être atteints au coût de -1 $ + 2 = 1 $. À ce stade, j'ai trouvé que je pouvais atteindre C à un coût inférieur via $ B $, donc je le mettrai à jour en $ C: 1 $. Faites cela pour tous les côtés. C'est la première fois. Après cela, si vous répétez (nombre de sommets-1) fois, vous pouvez partir de $ A $ et trouver le chemin le plus court vers tous les sommets.

Pourquoi le faites-vous (nombre de sommets-1) fois?

Le nombre maximum de sommets qui passent du point de départ à la destination correspond aux sommets à l'exclusion du point de départ, c'est-à-dire (nombre de sommets-1). Dans le processus décrit ci-dessus, le chemin le plus court (le sommet qui peut être déplacé du point de départ dans la première boucle) est toujours trouvé. Dans la deuxième boucle, le chemin le plus court (le sommet qui peut être déplacé de l'itinéraire déterminé la première fois) est ** toujours ** trouvé. ・ ・ ・ Après tout, cette boucle consiste à trouver l'itinéraire le plus court dans l'ordre à partir du point de départ, il est donc possible de trouver l'itinéraire le plus court par itinéraire de relaxation.

Si vous avez des problèmes en raison d'un poids négatif

Voir la figure ci-dessous. La partie encerclée est un cycle, mais si vous vous déplacez ici, le coût diminuera de -2. En d'autres termes, si vous utilisez ce cycle, vous pouvez réduire le coût à l'infini. C'est ce qu'on appelle la ** fermeture négative **.

La méthode de Bellmanford peut également détecter les routes fermées négatives. Plus tôt, j'ai confirmé que le chemin le plus court a été trouvé dans une boucle de (nombre de sommets-1) fois, mais le coût de tous les sommets est à nouveau calculé, et s'il existe un sommet qui peut mettre à jour le coût, il y a un chemin fermé négatif. Sera.

Montre-moi le code source

Il prend en charge l'entrée du format de liste de contiguïté (il existe également une matrice de contiguïté souvent utilisée chez les professionnels de la compétition) et détecte l'itinéraire le plus court par la méthode de Bellmanford. Voici un exemple d'entrée avec une fermeture négative sous le code (graphique dans la figure ci-dessus). Remplace le coût des sommets via la fermeture négative par $ -inf $.

<détails>

def shortest_path(s,n,es):
    #Distance la plus courte de s → i
    # s:point de départ, n:Nombre de sommets, es[i]: [辺のpoint de départ,Fin de côté,Coût secondaire]
    
    #Initialisation du poids. Notez la distance la plus courte ici
    d = [float("inf")] * n
    
    #Le point de départ est 0
    d[s] = 0

    #Calculez l'itinéraire le plus court
    for _ in range(n-1):
        # es:À propos du côté i[from,to,cost]
        for p,q,r in es:
            #Mis à jour si la racine de la flèche a été recherchée et qu'il existe un itinéraire coûtable
            if d[p] != float("inf") and d[q] > d[p] + r:
                d[q] = d[p] + r
    
    #Vérifier route fermée négative
    for _ in range(n-1):
        # e:À propos du côté i[from,to,cost]
        for p,q,r in es:
            #Parce que le point à mettre à jour est affecté par la fermeture négative-mettre inf
            if d[q] > d[p] + r:
                d[q] = -float("inf")
    return d
################
#contribution
n,w = map(int,input().split()) #n:Nombre de sommets w:Nombre de côtés

es = [] #es[i]: [Le point de départ du côté,Fin de côté,Coût secondaire]
for _ in range(w):
    x,y,z = map(int,input().split())
    es.append([x,y,z])
    # es.append([y,x,z])

print(shortest_path(0,n,es))

'''
contribution
7 12
0 1 2 
0 2 -5
0 3 5
1 2 3
1 4 1
1 5 3
2 4 6
3 2 -2
3 5 4
4 6 -5
5 4 -2
6 2 -3
'''
>>[0, 2, -inf, 5, -inf, 5, -inf]

import heapq

def dijkstra(s, n, es):
    #Distance la plus courte entre le point de départ s et chaque sommet
    #n:Nombre de sommets, cost[u][v] :Coût UV latéral(Inf quand il n'existe pas)
    d = [float("inf")] * n
    #Liste de recherche
    S = [s]
    #Les files d'attente prioritaires réduisent la quantité de calcul
    heapq.heapify(S)

    d[s] = 0
    
    while S:
        #Extraire le pic du coût le plus bas
        v = heapq.heappop(S)
        # print("-----------v", v)
        for u, w in es[v]:
            # print(u, w)
            #Mettre à jour si accessible à moindre coût et ajouter à la liste
            if d[u] > d[v]+w:
                d[u] = d[v]+w
                heapq.heappush(S, u)
        # print("d", d)
    return d

n,w = map(int,input().split()) #n:Nombre de sommets w:Nombre de côtés

cost = [[float("inf") for i in range(n)] for i in range(n)] 
es = [[] for _ in range(n)]

for i in range(w):
    x, y, z = map(int, input().split())
    es[x].append([y, z])
    es[y].append([x, z]) #Supprimer cette ligne pour les graphiques dirigés
# print(es)
print(dijkstra(0, n, es))

#Graphique de la méthode Dikstra
import matplotlib.pyplot as plt
import networkx as nx

#Ensemble de graphiques dirigés
G = nx.DiGraph()

#Ajouter des arêtes
# G.add_edges_from([("A", "B", {"weight":2)])
# nx.add_path(G, ["A", "C"])
# G.edges["A", "B"]["weight"] = 2
G.add_weighted_edges_from([("A", "B", 5), ("A", "C", 7), ("A", "D", 1), ("B", "C", 3), ("B", "F", 3), ("D", "B", 2)])
G.add_weighted_edges_from([("C", "E", 3), ("D", "F", 8), ("F", "E", 2), ("B", "E", 6)])

#Si vous ne spécifiez pas les coordonnées des sommets dans la figure, ils seront disposés au hasard.
pos1 = {}
pos1["A"] = (0, 0)
pos1["B"] = (1, 0)
pos1["C"] = (1, 2)
pos1["D"] = (1, -2)
pos1["E"] = (2, 1)
pos1["F"] = (2, -1)

#Si vous le dessinez tel quel, le caractère de poids sera un obstacle, alors effacez-le
edge_labels = {(i, j): w['weight'] for i, j, w in G.edges(data=True)}

#Écrire le poids
nx.draw_networkx_edge_labels(G, pos1, edge_labels=edge_labels, font_size=18)
#Dessin
nx.draw_networkx(G, pos1, node_size=1000, label_pos=100, node_color="r", font_size=18)
#Enregistrer la figure
plt.savefig("dijkstra.png ")
plt.show()

#La méthode Dyxtra est également implémentée dans networkx. Le montant du calcul est O(V^2+E)Tellement lent
pred, dist = nx.dijkstra_predecessor_and_distance(G, "A")
print(pred, dist)

>>{'A': [], 'B': ['D'], 'C': ['B'], 'D': ['A'], 'F': ['B'], 'E': ['F']} 
>>{'A': 0, 'D': 1, 'B': 3, 'C': 6, 'F': 6, 'E': 8}