Pourquoi l'algorithme de Dijkstra ne fonctionne-t-il pas pour les bords de poids négatifs?
Quelqu'un peut-il me dire pourquoi l'algorithme de Dijkstra pour le chemin le plus court de source unique suppose que les bords doivent être non négatifs.
Je ne parle que des bords et non des cycles de poids négatifs.
5 réponses
Rappelons que dans l'algorithme de Dijkstra, Une fois qu'un sommet est marqué comme " fermé "(et hors de l'ensemble ouvert) - l'algorithme a trouvé le chemin le plus court, et n'aura plus jamais à développer ce nœud-il suppose que le chemin développé vers ce chemin est le plus court.
Mais avec des poids négatifs - ce n'est peut-être pas vrai. Par exemple:
A
/ \
/ \
/ \
5 2
/ \
B--(-10)-->C
V={A,B,C} ; E = {(A,C,2), (A,B,5), (B,C,-10)}
Dijkstra de A développera D'abord C, et échouera plus tard à trouver A->B->C
Modifier un peu plus profond explication:
Notez que ceci est important, car à chaque étape de relaxation, l'algorithme suppose que le "coût" des nœuds "fermés" est en effet minime, et donc le nœud qui sera ensuite sélectionné est également minime.
L'idée est la suivante: si nous avons un sommet ouvert tel que son coût est minime - en ajoutant n'importe quel nombre positif à n'importe quel sommet - la minimalité ne changera jamais.
, Sans la contrainte sur les nombres positifs - l'hypothèse ci-dessus n'est pas vrai.
Puisque nous "connaissons" chaque sommet qui était "fermé "est minime - nous pouvons faire l'étape de relaxation en toute sécurité - sans"regarder en arrière". Si nous avons besoin de" regarder en arrière " - Bellman-Ford offre une solution de type récursif (DP) de le faire.
Considérez le graphique ci-dessous avec la source comme Vertex A. essayez D'abord d'exécuter l'algorithme de Dijkstra vous-même dessus.
Quand je me réfère à l'algorithme de Dijkstra dans mon explication, je parlerai de L'algorithme de Dijkstra tel qu'implémenté ci-dessous,
, Afin de commencer la valeurs (la distance entre la source et le sommet) initialement attribué à chaque sommet sont,
Nous tout d'abord extraire le sommet Q = [A,B,C], qui a la plus petite valeur, c'est à dire Un, après quoi Q = [B, C]. Note A a un bord dirigé vers B et C, aussi les deux sont dans Q, donc nous mettons à jour ces deux valeurs,
Maintenant, nous extrayons C comme (2 Q = [B] . Notez que C n'est connecté à rien, donc la boucle line16 ne s'exécute pas.
Enfin, nous avons extrait B, après quoi 
. Note B a un bord dirigé vers C mais C n'est pas présent dans Q donc nous n'entrons pas à nouveau la boucle for dans line16,
, Donc nous nous retrouvons avec les distances
Notez comment cela est faux car la distance la plus courte de A à C est 5 + -10 = -5, quand vous allez 
.
Donc, pour ce graphe, L'algorithme de Dijkstra calcule à tort la distance de A à C.
Cela se produit parce que Dijkstra L'algorithme n'essaie pas de trouver un chemin plus court vers les sommets qui sont déjà extraits de Q.
Ce Que fait la boucle line16 prend le Sommet u et dit "hey On dirait que nous pouvons aller àv de la source viau , est-ce que cette distance (alt ou alternative) est meilleure que la distance actuelle dist[v] que nous avons? Si donc permet de mettre à jour dist[v]"
Notez que dans line16 ils vérifient tous les voisins v (c'est à dire un dirigé bord existe à partir de u à v), de u sont toujours dans Q. Dans line14, Ils suppriment les notes visitées de Q. Donc, si x est un voisin visité de u , le chemin 
est même pas considéré {[22] } comme un moyen plus court possible de la source à v .
Ceci est en fait utile si les poids de bord sont tous des nombres positifs , car alors nous ne perdrions pas notre temps à considérer des chemins que ne peuvent pas soyez plus court.
Donc je dis que lors de l'exécution de cet algorithme si x est extrait de Q avant y , alors il n'est pas possible de trouver un chemin - 
ce qui est plus court. Permettez-moi d'expliquer cela avec un exemple,
, Comme y vient d'être extraite et x avait été extraite avant de lui-même, puis dist[y] > dist[x], car sinon y aurait été extraites avant de x. (line 13 distance min premier)
Et comme nous l'avons déjà supposé que les poids de bord sont positifs, c'est-à-dire Longueur(x,y)>0. Donc l'alternative à distance (alt) via y est toujours sûr d'être plus grand, c'est à dire dist[y] + longueur(x,y)> dist[x]. Ainsi, la valeur de dist [x] n'aurait pas été mise à jour même si y était considérée comme un chemin vers x , nous concluons donc qu'il est logique de ne considérer que les voisins de y qui sont toujours dans Q (note commentaire dans line16)
Mais cette chose dépend de notre hypothèse de longueur de bord positive, si length (u,v)dist [x] après la comparaison dans line18.
Pour tout dist[x] calcul sera incorrect si x est supprimé avant que tous les sommets v tels que x est un voisin de v négatives sur le bord de la connexion - est retiré.
Parce que chacun de ces sommets v est l'avant-dernier sommet sur un chemin potentiel "meilleur" de la source à x , qui est ignoré par l'algorithme de Dijkstra.
Donc, dans l'exemple que j'ai donné ci-dessus, l'erreur était parce que C a été supprimé avant que B ne soit supprimé. Alors que C était un voisin de B avec un bord négatif!
Juste pour clarifier, B et C sont les voisins de A. B a un seul voisin C et C n'a pas de voisins. longueur(a,b) est le bord longueur entre les sommets a et B.
L'algorithme de Dijkstra suppose que les chemins ne peuvent devenir "plus lourds", de sorte que si vous avez un chemin de A à B avec un poids de 3, et un chemin de A à C avec un poids de 3, Il n'y a aucun moyen d'ajouter un bord et d'aller de A à B à C avec un
Cette hypothèse rend l'algorithme plus rapide que les algorithmes qui doivent prendre en compte les poids négatifs.
L'Exactitude de l'algorithme de Dijkstra:
Nous avons 2 ensembles de sommets à n'importe quelle étape de l'algorithme. Set a se compose des sommets auxquels nous avons calculé les chemins Les plus courts. L'ensemble B comprend les sommets restants.
Hypothèse Inductive : à chaque étape, nous supposerons que toutes les itérations précédentes sont correctes.
Étape Inductive : lorsque nous ajoutons un sommet V à L'ensemble A et définissons la distance à dist [V], nous devons prouver que cette distance est optimal. Si ce n'est pas optimal, il doit y avoir un autre chemin vers le Sommet v qui est de longueur plus courte.
Supposons qu'un autre chemin passe par un sommet X.
Maintenant, depuis dist [V]
Ainsi, pour que l'algorithme de dijkstra fonctionne, les poids des arêtes doivent être non négatifs.
Essayez l'algorithme de Dijkstra sur le graphique suivant, en supposant que A est le nœud source, pour voir ce qui se passe:
