Poids négatifs utilisant l'algorithme de Dijkstra

113

J'essaie de comprendre pourquoi l'algorithme de Dijkstra ne fonctionnera pas avec des poids négatifs. En lisant un exemple sur les chemins les plus courts , j'essaie de comprendre le scénario suivant:

    2
A-------B
 \     /
3 \   / -2
   \ /
    C

Depuis le site Web:

En supposant que les arêtes sont toutes dirigées de gauche à droite, si nous commençons par A, l'algorithme de Dijkstra choisira l'arête (A, x) minimisant d (A, A) + longueur (arête), à ​​savoir (A, B). Il pose alors d (A, B) = 2 et choisit une autre arête (y, C) minimisant d (A, y) + d (y, C); le seul choix est (A, C) et il fixe d (A, C) = 3. Mais il ne trouve jamais le chemin le plus court de A à B, via C, avec une longueur totale de 1.

Je ne peux pas comprendre pourquoi en utilisant l'implémentation suivante de Dijkstra, d [B] ne sera pas mis à jour en 1(Lorsque l'algorithme atteint le sommet C, il exécutera un relâchement sur B, voir que le d [B] est égal à 2, et donc mettre à jour sa valeur à 1).

Dijkstra(G, w, s)  {
   Initialize-Single-Source(G, s)
   S ← Ø
   Q ← V[G]//priority queue by d[v]
   while Q ≠ Ø do
      u ← Extract-Min(Q)
      S ← S U {u}
      for each vertex v in Adj[u] do
         Relax(u, v)
}

Initialize-Single-Source(G, s) {
   for each vertex v  V(G)
      d[v] ← ∞
      π[v] ← NIL
   d[s] ← 0
}

Relax(u, v) {
   //update only if we found a strictly shortest path
   if d[v] > d[u] + w(u,v) 
      d[v] ← d[u] + w(u,v)
      π[v] ← u
      Update(Q, v)
}

Merci,

Meir

Meir
la source
La recherche de trajectoire en général avec des poids de bord négatifs est extrêmement difficile. Quel que soit l'itinéraire que vous trouvez, il y a toujours la possibilité d'un itinéraire arbitrairement long avec un poids de bord négatif arbitrairement grand quelque part le long de celui-ci. Je ne serais pas surpris si c'est NP complet.
Nick Johnson
4
Pour toute autre personne ayant ce doute, vous pouvez trouver le chemin le plus court dans un graphique DONNÉ qu'il n'a pas de cycles de poids négatifs. L'algorithme ci-dessus fonctionnerait si la fonction Relax retournait une valeur "true" lorsque la relaxation réussissait réellement, auquel cas le sommet adjacent "v" serait mis en file d'attente dans la file d'attente prioritaire s'il n'est pas présent, ou mis à jour s'il est déjà présent. Cela signifie que les nœuds visités peuvent à nouveau être ajoutés à la file d'attente prioritaire au fur et à mesure qu'ils se relâchent.
goelakash

Réponses:

202

L'algorithme que vous avez suggéré trouvera en effet le chemin le plus court dans ce graphique, mais pas tous les graphiques en général. Par exemple, considérez ce graphique:

Figure de graphique

Supposons que les bords soient dirigés de gauche à droite comme dans votre exemple,

Votre algorithme fonctionnera comme suit:

  1. Tout d'abord, vous définissez d(A)sur zeroet les autres distances sur infinity.
  2. Vous développez ensuite le nœud Aen définissant d(B)vers 1, d(C)vers zeroet d(D)vers 99.
  3. Ensuite, vous développez C, sans changements nets.
  4. Vous vous développez ensuite B, ce qui n'a aucun effet.
  5. Enfin, vous développez D, qui change d(B)à -201.

Notez qu'à la fin de cela, cependant, c'est d(C)toujours 0, même si le chemin le plus court Ca une longueur -200. Votre algorithme ne parvient donc pas à calculer avec précision les distances dans certains cas. De plus, même si vous deviez stocker des pointeurs de retour indiquant comment passer de chaque nœud au nœud de départ A, vous finiriez par prendre le mauvais chemin de retour de Cà A.

templatetypedef
la source
35
Pour ajouter à votre excellente réponse: Dijkstra étant un algorithme gourmand est la raison de son choix à courte vue.
blubb
4
Je tiens à souligner que, techniquement, tous les chemins de ce graphique ont un coût de l'infini négatif grâce au cycle négatif A, D, B, A.
Nate
2
@ Nate- Pour clarifier, toutes les arêtes du graphique sont dirigées de gauche à droite. C'était un peu difficile de rendre des flèches dans mon art ASCII de haute qualité. :-)
templatetypedef
2
Pour ceux qui n'ont jamais vu de graphiques avec des bords négatifs auparavant, je trouve qu'une interprétation utile de ce graphique est un réseau de routes à péage, où les poids de bord donnent le péage que vous payez. La route -300 est une route à péage arrière folle où ils vous donnent 300 $ à la place.
D Coetzee
3
@ SchwitJanwityanujit - C'est ainsi que fonctionne l'algorithme de Dijkstra. L'algorithme n'explore pas les chemins , mais fonctionne à la place en traitant les nœuds . Chaque nœud est traité exactement une fois, donc dès que nous traitons le nœud B et que nous obtenons que sa distance est de 1, nous ne revisiterons jamais le nœud B ni ne tenterons de mettre à jour sa distance.
templatetypedef
25

Notez que Dijkstra fonctionne même pour les poids négatifs, si le graphique n'a pas de cycles négatifs, c'est-à-dire des cycles dont le poids additionné est inférieur à zéro.

Bien sûr, on pourrait se demander pourquoi dans l'exemple fait par templatetypedef Dijkstra échoue même s'il n'y a pas de cycles négatifs, en fait pas même de cycles. C'est parce qu'il utilise un autre critère d'arrêt, qui contient l'algorithme dès que le nœud cible est atteint (ou que tous les nœuds ont été réglés une fois, il ne l'a pas spécifié exactement). Dans un graphique sans poids négatifs, cela fonctionne très bien.

Si l'on utilise le critère d'arrêt alternatif, qui arrête l'algorithme lorsque la file d'attente de priorité (tas) est vide (ce critère d'arrêt a également été utilisé dans la question), alors dijkstra trouvera la distance correcte même pour les graphiques avec des poids négatifs mais sans cycles négatifs.

Cependant, dans ce cas, la limite temporelle asymptotique de dijkstra pour les graphes sans cycles négatifs est perdue. En effet, un nœud précédemment réglé peut être réinséré dans le tas lorsqu'une meilleure distance est trouvée en raison de poids négatifs. Cette propriété est appelée correction d'étiquette.

infty10000101
la source
2. On ne sait pas pourquoi vous pensez que le temps me ferait "plus comme Bellman-Ford" et non pas exponentiel (ce qui est pire que Bellman-Ford). Avez-vous un algorithme concret et une preuve en tête?
Gassa
3
À 1.: comme vous pouvez utiliser exactement la même implémentation de dijkstra avec le critère d'arrêt mentionné, qui s'arrête lorsque la file d'attente est vide (voir le pseudocode dans la question d'origine), c'est toujours l'algorithme dijkstras pour les chemins les plus courts, même s'il se comporte différemment pose plusieurs fois des nœuds (correction d'étiquettes).
infty10000101
1
À 2.: C'était juste une supposition donc je vais supprimer cela. Je pense que vous avez raison avec le temps exponentiel, car il y a exponentiellement de nombreux chemins qui doivent être explorés.
infty10000101
11

vous n'avez utilisé S nulle part dans votre algorithme (en plus de le modifier). l'idée de dijkstra est qu'une fois qu'un sommet est sur S, il ne sera plus jamais modifié. dans ce cas, une fois que B est à l'intérieur de S, vous ne l'atteindrez plus via C.

ce fait assure la complexité de O (E + VlogV) [sinon, vous répéterez les arêtes plus d'une fois, et les sommets plus d'une fois]

en d'autres termes, l'algorithme que vous avez posté peut ne pas être en O (E + VlogV), comme promis par l'algorithme de dijkstra.

amit
la source
De plus, il n'est pas nécessaire de modifier le sommet sans arêtes de poids négatifs, ce qui rompt complètement l'hypothèse selon laquelle les coûts de chemin ne peuvent augmenter qu'avec des arêtes répétées
prusswan
cette hypothèse est exactement ce qui nous permet d'utiliser S, et «savoir» une fois qu'un sommet est dans S, il ne sera plus jamais modifié.
amit le
Votre dernière déclaration est fausse. L'algorithme affiché a une complexité temporelle O (E + VlogV) lorsqu'il fonctionne sur des graphiques sans bords négatifs. Il n'est pas nécessaire de vérifier que nous avons déjà visité un nœud, car le fait qu'il a été visité garantit que la procédure de relaxation ne l'ajoutera pas une fois de plus dans la file d'attente.
Pixar
7

Puisque Dijkstra est une approche gourmande, une fois qu'un sommet est marqué comme visité pour cette boucle, il ne sera plus jamais réévalué même s'il existe un autre chemin moins coûteux pour l'atteindre plus tard. Et un tel problème ne peut se produire que lorsque des arêtes négatives existent dans le graphique.


Un algorithme gourmand , comme son nom l'indique, fait toujours le choix qui semble être le meilleur à ce moment-là. Supposons que vous ayez une fonction objective qui doit être optimisée (maximisée ou minimisée) à un moment donné. Un algorithme Greedy fait des choix gourmands à chaque étape pour s'assurer que la fonction objectif est optimisée. L'algorithme Greedy n'a qu'un seul coup pour calculer la solution optimale afin qu'il ne revienne jamais en arrière et annule la décision.

punchoyeah
la source
4

TL; DR: La réponse dépend de votre implémentation. Pour le pseudo code que vous avez publié, il fonctionne avec des pondérations négatives.


Variantes de l'algorithme de Dijkstra

La clé est qu'il existe 3 types d'implémentation de l'algorithme de Dijkstra , mais toutes les réponses sous cette question ignorent les différences entre ces variantes.

  1. Utilisation d'une boucle imbriquéefor pour détendre les sommets. C'est le moyen le plus simple d'implémenter l'algorithme de Dijkstra. La complexité temporelle est O (V ^ 2).
  2. Implémentation basée sur la file d'attente prioritaire / le tas + PAS de rentrée autorisée, où la rentrée signifie qu'un sommet relâché peut être poussé à nouveau dans la file d'attente prioritaire pour être relâché plus tard .
  3. Implémentation basée sur la file d'attente / tas de priorité + rentrée autorisée.

Les versions 1 et 2 échoueront sur les graphiques avec des poids négatifs (si vous obtenez la bonne réponse dans de tels cas, ce n'est qu'une coïncidence), mais la version 3 fonctionne toujours .

Le pseudo code publié sous le problème d'origine est la version 3 ci-dessus, il fonctionne donc avec des poids négatifs.

Voici une bonne référence d' Algorithm (4e édition) , qui dit (et contient l'implémentation java des versions 2 et 3 que j'ai mentionnées ci-dessus):

Q. L'algorithme de Dijkstra fonctionne-t-il avec des poids négatifs?

R. Oui et non. Il existe deux algorithmes de chemins les plus courts connus sous le nom d'algorithme de Dijkstra, selon qu'un sommet peut être mis en file d'attente plusieurs fois dans la file d'attente prioritaire. Lorsque les pondérations sont non négatives, les deux versions coïncident (car aucun sommet ne sera mis en file d'attente plus d'une fois). La version implémentée dans DijkstraSP.java (qui permet à un sommet d'être mis en file d'attente plus d'une fois) est correcte en présence de poids de bord négatifs (mais pas de cycles négatifs) mais son temps d'exécution est exponentiel dans le pire des cas. (Nous notons que DijkstraSP.java lève une exception si le digraphe pondéré par les bords a un bord avec un poids négatif, de sorte qu'un programmeur ne soit pas surpris par ce comportement exponentiel.) Si nous modifions DijkstraSP.java afin qu'un sommet ne puisse pas être mis en file d'attente plus d'une fois (par exemple, en utilisant un tableau marqué [] pour marquer les sommets qui ont été relâchés),


Pour plus de détails sur l'implémentation et la connexion de la version 3 avec l'algorithme Bellman-Ford, veuillez consulter cette réponse de zhihu . C'est aussi ma réponse (mais en chinois). Actuellement, je n'ai pas le temps de le traduire en anglais. J'apprécie vraiment que quelqu'un puisse le faire et modifier cette réponse sur stackoverflow.

solo
la source
1

Considérez ce qui se passe si vous faites des allers-retours entre B et C ... voila

(pertinent uniquement si le graphique n'est pas orienté)

Édité: Je pense que le problème est lié au fait que le chemin avec AC * ne peut être meilleur que AB avec l'existence d'arêtes de poids négatives, donc peu importe où vous allez après AC, avec l'hypothèse de non- les bords de poids négatifs, il est impossible de trouver un chemin meilleur que AB une fois que vous avez choisi d'atteindre B après être passé à AC.

Prusswan
la source
ce n'est pas possible, le graphique est orienté.
amit le
@amit: bon point, j'ai raté ça. Il est temps de reconsidérer le problème
Prusswan
1

"2) Pouvons-nous utiliser l'algorithme de Dijksra pour les chemins les plus courts pour les graphiques avec des poids négatifs - une idée peut être, calculer la valeur de poids minimum, ajouter une valeur positive (égale à la valeur absolue de la valeur de poids minimum) à tous les poids et exécuter l'algorithme de Dijksra pour le graphique modifié. Cet algorithme fonctionnera-t-il? "

Cela ne fonctionne absolument pas à moins que tous les chemins les plus courts aient la même longueur. Par exemple, étant donné un chemin le plus court de longueur deux bords, et après avoir ajouté une valeur absolue à chaque bord, le coût total du chemin est augmenté de 2 * | poids négatif maximum |. D'autre part un autre chemin de longueur trois bords, donc le coût du chemin est augmenté de 3 * | poids négatif max |. Par conséquent, tous les chemins distincts sont augmentés de quantités différentes.

Wackyfool
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