Poids négatifs à l'aide de l'algorithme de Dijkstra

Question

J'essaie de comprendre pourquoi l'algorithme de Dijkstra ne fonctionne 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

Extrait du site web :

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

Je ne comprends pas 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écute un relax sur B, voit que le d[B] est égal à 2 et donc de 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)
}

Gracias,

Meir

Answer 1

L'algorithme que vous avez suggéré trouvera effectivement le plus court chemin dans ce graphe, mais pas tous les graphes en général. Par exemple, considérons ce graphe :

Retraçons l'exécution de votre algorithme.

1. Tout d'abord, vous définissez d( A ) à 0 et les autres distances à .
2. Vous élargissez ensuite le nœud A , en fixant d( B ) à 1, d( C ) à 0, et d( D ) à 99.
3. Ensuite, vous élargissez C sans aucun changement net.
4. Vous vous étendez ensuite B qui n'a aucun effet.
5. Enfin, vous élargissez D ce qui modifie d( B ) à -201.

Remarquez qu'à la fin, cependant, que d( C ) est toujours égal à 0, même si le chemin le plus court vers C a une longueur de -200. Cela signifie que votre algorithme ne calcule pas les distances correctes à tous les nœuds. De plus, même si vous stockiez des pointeurs indiquant comment aller de chaque nœud au nœud de départ A vous finirez par prendre le mauvais chemin pour revenir de C a A .

La raison en est que l'algorithme de Dijkstra (et votre algorithme) sont algorithmes avides qui partent du principe qu'une fois qu'ils ont calculé la distance d'un nœud, la distance trouvée doit être la distance optimale. En d'autres termes, l'algorithme ne se permet pas de prendre la distance d'un nœud qu'il a développé et de modifier cette distance. Dans le cas d'arêtes négatives, votre algorithme, et l'algorithme de Dijkstra, peuvent être "surpris" en voyant une arête à coût négatif qui diminuerait effectivement le coût du meilleur chemin du nœud de départ à un autre nœud.

J'espère que cela vous aidera !

Answer 2

Notez que Dijkstra fonctionne même pour des poids négatifs, si le graphe n'a pas de cycles négatifs, c'est-à-dire des cycles dont la somme des poids est inférieure à zéro.

Bien sûr, on peut se demander pourquoi, dans l'exemple donné par templatetypedef, Dijkstra échoue alors qu'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 arrête 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 précisé exactement). Dans un graphe sans poids négatifs, cela fonctionne bien.

Si l'on utilise le critère d'arrêt alternatif, qui arrête l'algorithme lorsque la file d'attente des priorités (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 graphes avec des poids négatifs mais sans cycles négatifs.

Cependant, dans ce cas, la limite de temps asymptotique de dijkstra pour les graphes sans cycles négatifs est perdue. Cela est dû au fait qu'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 des poids négatifs. Cette propriété est appelée correction d'étiquette.

Answer 3

Je comprends la question de l'OP comme suit pourquoi L'algorithme de Dijkstra échoue dans ce cas. Voyons voir.

Tout d'abord, la déclaration correcte est que "l'algorithme de Dijkstra échoue s'il y a des négatifs dirigé bords". S'il y a des non orienté alors chaque bord négatif constitue immédiatement un bord négatif. cycle ( X->Y->X ), et le graphique ne ont un chemin le plus court et la question est discutable.

Pour que cela ne soit pas trivial, supposons que le graphe soit orienté :

A -> B : 2
A -> C : 3
C -> B : -2

Supposons encore que notre source soit A . Le vrai plus court chemin de A à B est A-C-B avec un poids de 1. Mais l'algorithme de Dijkstra commence par sélectionner A->B et supprime ensuite cet avantage de toute considération future. parce qu'elle suppose qu'elle ne peut pas être améliorée .

Ceci est crucial : Sous l'hypothèse de non-négativité, nous pouvons être sûrs une fois pour toutes que le plus court chemin de A à B est A -> B : 2 . Comme l'algorithme suppose cela, il ne vérifie jamais plus tard s'il existe un chemin encore plus court, car avec des arêtes non négatives, il ne peut pas y en avoir.

Cette hypothèse permet à l'algorithme de procéder avec moins d'étapes, mais elle l'empêche d'identifier correctement le plus court chemin en présence d'arêtes négatives. Les bords négatifs rendent le problème "non local" dans le sens où vous ne pouvez pas savoir si vous vous en sortez bien en regardant simplement vos voisins immédiats - il pourrait toujours y avoir un bord extrêmement négatif juste après ce bord très cher à côté de vous.

Answer 4

Vous n'avez utilisé S nulle part dans votre algorithme (à part 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 dans S, vous ne l'atteindrez plus via C.

ce fait garantit une 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é, pourrait ne pas être en O(E+VlogV), comme promis par l'algorithme de dijkstra.

Answer 5

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

(pertinent uniquement si le graphe n'est pas dirigé)

Modifié : Je crois que le problème est lié au fait que le chemin avec AC* ne peut être meilleur que AB qu'avec l'existence d'arêtes de poids négatif, donc peu importe où vous allez après AC, avec l'hypothèse d'arêtes de poids non négatif il est impossible de trouver un chemin meilleur que AB une fois que vous avez choisi d'atteindre B après avoir fait AC.