Pourquoi l'algorithme de Dijkstra ne fonctionne-t-il pas pour les bords de poids négatifs?

121

Quelqu'un peut-il me dire pourquoi l'algorithme de Dijkstra pour le plus court chemin à source unique suppose que les arêtes doivent être non négatives.

Je ne parle que des bords et non des cycles de poids négatifs.

Madu
la source
3
Une réponse correcte avec un bon exemple serait: stackoverflow.com/questions/6799172/…
Amitk

Réponses:

175

Rappelez-vous 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 vers lui , et n'aura plus jamais à développer ce nœud - il suppose le chemin développé pour cela le 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 ne parviendra plus tard à trouver A->B->C


ÉDITER une explication un peu plus profonde:

Notez que cela est important, car à chaque étape de relaxation, l'algorithme suppose que le «coût» pour les 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 de sorte que son coût soit minimal - en ajoutant un 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 vraie.

Puisque nous «savons» que chaque sommet qui était «fermé» est minimal - nous pouvons faire l'étape de relaxation en toute sécurité - sans «regarder en arrière». Si nous devons "regarder en arrière" - Bellman-Ford propose une solution de type récursif (DP) pour le faire.

amit
la source
5
Désolé mais je n'obtiens aucune erreur. Tout d' abord A->Bsera 5 et A->Csera 2. Ensuite B->Cvolonté -5. La valeur de Csera donc la -5même que celle de bellman-ford. Comment cela ne donne-t-il pas la bonne réponse?
Anirban Nag 'tintinmj'
5
@tintinmj d'abord, Dijkstra "fermera" le nœud Aavec la valeur 0. Ensuite, il recherchera le nœud à valeur minimale, Best 5 et Cvaut 2. Le minimum est C, donc il se fermera Cavec la valeur 2 et ne regardera jamais en arrière, quand Best fermé plus tard , il ne peut pas modifier la valeur de C, car il est déjà "fermé".
amit
4
@amit Comment l'algorithme de Dijkstra ne trouve pas le chemin A -> B -> C? Il mettra d'abord à jour Cla distance à 2, puis Bla distance à 5. En supposant que dans votre graphique il n'y a pas d'arêtes sortantes C, alors nous ne faisons rien lors de la visite C(et sa distance est toujours de 2). Ensuite, nous visitons Dles nœuds adjacents, et le seul nœud adjacent est C, dont la nouvelle distance est -5. Notez que dans l'algorithme de Dijkstra, nous gardons également une trace du parent à partir duquel nous atteignons (et mettons à jour) le nœud, et en le faisant C, vous obtiendrez le parent B, puis A, résultant en un résultat correct. Qu'est-ce que je rate?
nbro
12
@amit Le problème avec votre raisonnement (je pense), et j'ai vu d'autres personnes le faire (étrangement), c'est que vous pensez que l'algorithme ne reconsidérera pas les nœuds dont la distance la plus courte a déjà été déterminée (et dont nous en avons fini), mais ce n'est pas correct, et c'est pourquoi nous avons l'étape de "relaxation" ... Nous parcourons tous les nœuds du graphe, et, pour chacun d'eux, nous parcourons les nœuds adjacents, même si l'un des nœuds adjacents pourrait ont déjà été supprimés de notre file d'attente à priorité minimale, par exemple.
nbro
10
@amit Cochez cette réponse à une question similaire, où l'exemple a vraiment du sens: stackoverflow.com/a/6799344/3924118
nbro
37

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.

entrez la description de l'image ici

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,

Algorithme de Dijkstra

Donc, en commençant par les valeurs ( la distance de la source au sommet ) initialement affectées à chaque sommet sont,

initialisation

On extrait d'abord le sommet de Q = [A, B, C] qui a la plus petite valeur, c'est-à-dire A, après quoi Q = [B, C] . Remarque A a un bord dirigé vers B et C, les deux sont également en Q, nous mettons donc à jour ces deux valeurs,

première itération

Maintenant, nous extrayons C comme (2 <5), maintenant Q = [B] . Notez que C n'est connecté à rien, donc la line16boucle ne s'exécute pas.

deuxième itération

Enfin, nous extrayons B, après quoi Q est Phi. Remarque B a une arête dirigée vers C mais C n'est pas présent dans Q donc nous n'entrons pas à nouveau la boucle for dans line16,

3e?

Donc nous nous retrouvons avec les distances comme

pas de changement les gars

Remarquez comment cela est faux car la distance la plus courte entre A et C est 5 + -10 = -5, lorsque vous y allez a à b à c.

Donc, pour ce graphique, l'algorithme de Dijkstra calcule à tort la distance de A à C.

Cela se produit parce que l'algorithme de Dijkstra n'essaye pas de trouver un chemin plus court vers des sommets déjà extraits de Q .

Ce que fait la line16boucle, c'est de prendre le sommet u et de dire "hey on dirait que nous pouvons aller vers v depuis la source via u , est-ce que cette distance (alt ou alternative) est meilleure que la dist [v] actuelle que nous avons? Si oui, mettons à jour dist [v] "

Notez que line16ils vérifient tous les voisins v (soit un bord dirigé existe de u à v ), de u qui sont encore en Q . Dans line14ils suppriment les notes visitées de Q. Donc, si x est un voisin visité de u , le chemin source vers u vers xn'est même pas considéré comme un chemin plus court possible de la source à v .

Dans notre exemple ci-dessus, C était un voisin visité de B, donc le chemin A à B à Cn'a pas été considéré, laissant le chemin le plus court actuel A à Cinchangé.

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 qui ne peuvent pas être plus courts.

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 -pas possible qui est plus court. Laissez-moi vous expliquer cela avec un exemple,

Comme y vient d'être extrait et que x a été extrait avant lui-même, alors dist [y]> dist [x] car sinon y aurait été extrait avant x . ( line 13distance minimale en premier)

Et comme nous avons déjà supposé que les poids des bords sont positifs, c'est-à-dire longueur (x, y)> 0 . Ainsi, la distance alternative (alt) via y est toujours sûre d'être plus grande, 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é comme un chemin vers x , nous concluons donc qu'il est logique de ne considérer que les voisins de y qui sont encore dans Q (notez le commentaire dans line16)

Mais cette chose dépend de notre hypothèse de longueur du bord positif, si length (u, v) <0, alors en fonction du degré de négatif de ce bord, nous pourrions remplacer le dist [x] après la comparaison dansline18 .

Donc, tout calcul de dist [x] que nous faisons sera incorrect si x est supprimé avant tous les sommets v - de sorte que x est un voisin de v avec un bord négatif les reliant - soient supprimés.

Parce que chacun de ces v sommets est l'avant-dernier sommet d'un "meilleur" chemin potentiel de la source à x , qui est écarté 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 voisin. length (a, b) est la longueur d'arête entre les sommets a et b.

Aditya P
la source
2
Comme vous l'avez dit, la meilleure façon de résoudre ce problème est d'utiliser la méthode heapq.heappush après chaque comparaison. Nous repoussons la distance mise à jour dans la file d'attente. Sous cette condition, les Dijkstra peuvent travailler sur des poids négatifs. J'ai essayé, et le résultat est sorti comme 0,5, -5
nosense
1
"le chemin source de x vers u n'est même pas considéré"; vouliez-vous dire source de u à x?
slmatrix
1
@slmatrix merci d'avoir attrapé cela, oui, je voulais dire que le chemin de la source à u vers x, car x est un voisin de u.
Aditya P du
23

L'algorithme de Dijkstra suppose que les chemins ne peuvent que 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, vous ne pouvez pas ajouter un bord et aller de A à B en passant par C avec un poids inférieur à 3.

Cette hypothèse rend l'algorithme plus rapide que les algorithmes qui doivent prendre en compte des poids négatifs.

zmbq
la source
8

Exactitude de l'algorithme de Dijkstra:

Nous avons 2 ensembles de sommets à n'importe quelle étape de l'algorithme. L'ensemble A est constitué 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 fixons la distance à dist [V], nous devons prouver que cette distance est optimale. Si ce n'est pas optimal, il doit y avoir un autre chemin vers le sommet V qui est de plus courte longueur.

Supposons qu'un autre chemin passe par un sommet X.

Maintenant, puisque dist [V] <= dist [X], donc tout autre chemin vers V aura au moins une longueur dist [V], à moins que le graphe n'ait des longueurs d'arêtes négatives.

Ainsi, pour que l'algorithme de dijkstra fonctionne, les poids de bord doivent être non négatifs.

Nikunj Banka
la source
6

Essayez l'algorithme de Dijkstra sur le graphique suivant, en supposant qu'il As'agit du nœud source, pour voir ce qui se passe:

Graphique

tb-
la source
6
Désolé mais je n'obtiens aucune erreur. Première A->Bvolonté 1et A->Cvolonté 100. Puis le B->Dfera 2. Puis le C->Dfera -4900. La valeur de Dsera donc la -4900même que celle de bellman-ford. Comment cela ne donne-t-il pas la bonne réponse?
Anirban Nag 'tintinmj'
9
@tintinmj Si vous avez un front sortant de D, il sera visité avant que la distance de D ne soit diminuée et donc pas mis à jour après. Cela entraînera alors une erreur à coup sûr. Si vous considérez D 2 comme la distance finale déjà après avoir scanné les bords sortants, même ce graphique entraîne une erreur.
Christian Schnorr
@ tb- Désolé d'avoir demandé après si longtemps, mais suis-je sur la bonne voie ici? Le premier A->Bsera 1et A->Csera 100. Puis Best exploré et se met B->Dà 2. Alors D est exploré parce qu'actuellement, il a le chemin le plus court vers la source? Aurais-je raison de dire que si B->Dc'était le cas 100, Caurais-je été exploré en premier? Je comprends tous les autres exemples que les gens donnent sauf le vôtre.
Pejman Poh
@PejmanPoh d'après ce que je comprends, si B-> D était 100, puisque A-> C est plus haut dans la HeapStructure qui sera utilisée, l'extraction min retournera A-> C en premier, ce qui signifie que le prochain chemin le plus court trouvé sera le chemin vers C, après cela, le chemin de C-> D qui a un poids de -5000 sera le choix évident, nous conduisant à la conclusion que le chemin le plus court serait de A-> C-> D et je suis à peu près sûr que ce serait être le comportement normal. Donc, parfois, lorsque nous avons des cycles négatifs, nous pouvons toujours obtenir la bonne valeur pour le chemin le plus court, mais certainement pas toujours, c'est un exemple où nous ne le ferons pas ..
T.Dimitrov
1

Rappelez-vous que dans l'algorithme de Dijkstra, une fois qu'un sommet est marqué comme «fermé» (et hors de l'ensemble ouvert) - il suppose que tout nœud en provenance de celui-ci conduira à une plus grande distance donc, l'algorithme a trouvé le chemin le plus court vers lui, et va ne jamais avoir à développer à nouveau ce nœud, mais cela n'est pas vrai en cas de poids négatifs.

vigne
la source
0

Les autres réponses jusqu'à présent démontrent assez bien pourquoi l'algorithme de Dijkstra ne peut pas gérer les poids négatifs sur les chemins.

Mais la question elle-même repose peut-être sur une mauvaise compréhension du poids des chemins. Si les poids négatifs sur les chemins étaient autorisés dans les algorithmes de recherche de chemin en général, vous obtiendriez des boucles permanentes qui ne s'arrêteraient pas.

Considère ceci:

A  <- 5 ->  B  <- (-1) ->  C <- 5 -> D

Quel est le chemin optimal entre A et D?

Tout algorithme de recherche de chemin devrait faire une boucle continue entre B et C car cela réduirait le poids du chemin total. Ainsi, autoriser des poids négatifs pour une connexion rendrait tout algorithme pathfindig inutile, peut-être sauf si vous limitez chaque connexion à être utilisée une seule fois.

Dakkaron
la source
0

Vous pouvez utiliser l'algorithme de dijkstra avec des arêtes négatives n'incluant pas le cycle négatif, mais vous devez autoriser qu'un sommet puisse être visité plusieurs fois et cette version perdra sa complexité en temps rapide.

Dans ce cas, j'ai pratiquement vu qu'il était préférable d'utiliser l' algorithme SPFA qui a une file d'attente normale et peut gérer les bords négatifs.

CodingLab
la source