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 image.png 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
image.png 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,

image.png

À 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. image.png 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>

Cliquez pour voir </ summary>

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]

Le montant du calcul est $ O (V ^ 2 + E) $ (nombre de sommets: $ V $, nombre de côtés: $ E $).

Quelle est la méthode Dyxtra?

Il peut être utilisé dans les graphiques avec des poids non négatifs.

Le processus de recherche de l'itinéraire le plus court est la [vidéo de Yobinori](![Image.png](https://qiita-image-store.s3.ap-northeast-1.amazonaws.com/0/411380/a8c60f68-abfc- d92b-02bb-b915e8b8da19.png) ) Est si facile à comprendre qu'il meurt. (La portée défensive de Yobinori est trop large ...)

Je vais l'expliquer ici aussi. image.png

Soit le coût du sommet (valeur initiale: $ S = 0 $, autre $ = ∞ $).

  1. Commencez par le sommet le moins coûteux. Initialement, $ S $ est le point de départ.

  2. Déterminez le coût du point de départ (vert sur la figure). Le coût de ce sommet ne sera plus mis à jour.

  3. Notez le coût du point de départ + les pondérations latérales sur les sommets qui peuvent être déplacés à partir du point de départ. Noté 7, 3, 1 $ en haut de la rangée du milieu. Le coût est incertain car il peut encore être mis à jour.

  4. Répétez les étapes 1 à 3 jusqu'à ce que tous les sommets soient confirmés. Parmi les sommets notés, celui avec le coût de 1 est le plus petit, alors confirmez-le et notez les sommets qui peuvent être déplacés à partir de ce sommet. Si vous pouvez déménager à moindre coût, mettez à jour le coût.

Pourquoi le trajet le plus court est-il nécessaire?

** Celui dont le coût est le plus bas parmi les sommets indéterminés ne peut pas être mis à jour à un coût inférieur **. Comme il n'y a que des pondérations non négatives, même si vous empruntez un autre itinéraire, le coût sera de 0 ou plus. Par conséquent, parmi les indéterminés, le coût le plus petit peut être déterminé comme l'itinéraire le plus court.

Alors, quel est le code source?

<détails>

Cliquez pour voir </ summary>

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))
Le montant initial du calcul est $ O (V ^ 2) $, qui est identique à la méthode de Bellmanford, mais il peut être réduit à $ O ((E + V) logV) $ en utilisant une file d'attente prioritaire.

Références ou sites

・ Introduction à l'algorithme 3e édition Volume 2: Méthode avancée de conception et d'analyse ・ Structure de données avancée ・ Algorithme graphique (manuel du MIT standard mondial) (T. Colmen, R. Rivest, C. Stein, C. Riserson, Tetsuo Asano, Kazuo Iwano, Hiroshi Umeo, Masashi Yamashita, Koichi Wada) C'est un livre assez lourd, mais la preuve de la théorie des graphes était très polie.

・ Théorie des graphes ⑤ (algorithme de Dixtra) ("Maths et physique universitaires" appris à l'école préparatoire) https://www.youtube.com/watch?v=X1AsMlJdiok Vous pouvez pleinement comprendre la méthode Dyxtra simplement en regardant cette vidéo!

・ Programmation de compétition Arimoto Python Single Route Méthode 2 (Méthode Dyxtra) (Le blog et le code de Juppy sont ici.) https://juppy.hatenablog.com/entry/2018/11/01/%E8%9F%BB%E6%9C%AC_python_%E5%8D%98%E4%B8%80%E6%9C%80%E7%9F%AD%E7%B5%8C%E8%B7%AF%E6%B3%952%EF%BC%88%E3%83%80%E3%82%A4%E3%82%AF%E3%82%B9%E3%83%88%E3%83%A9%E6%B3%95%EF%BC%89_%E7%AB%B6%E6%8A%80%E3%83%97

prime

Le graphique de l'article a été dessiné avec networkx. Je vais mettre le code pour ceux qui s'en soucient.

<détails>

Cliquez pour voir </ summary>

#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}

Recommended Posts