Poids négatifs utilisant l'algorithme de Dijkstra

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

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:

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.

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.

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.

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.

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.

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.

"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.

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.