Dijkstra avec des bords négatifs. Je ne comprends pas les exemples, ils fonctionnent selon le pseudocode CLRS

Question

EDIT 2:Il semble que ce n'est pas de CLRS (je suppose que c'était parce qu'il a suivi le même format de code CLRS qui nous a été donné dans ce Algos et DS cours). Néanmoins, dans ce cours, nous avons donné ce code comme étant "Algorithme de Dijkstra".

J'ai lu Why doesn't Dijkstra's algorithm work for negative weight edges? et Negative weights using Dijkstra's Algorithm (la seconde est spécifique à l'algorithme de l'OP je pense). En regardant le pseudo-code de CLRS ("Introduction aux algorithmes"), je ne comprends pas pourquoi Dijkstra ne fonctionnerait pas sur ces exemples de graphes avec des bords négatifs.

Dans le pseudo-code (ci-dessous), Insert nœuds de retour sur le tas si la nouvelle distance à eux est plus courte que la distance précédente à eux, donc il me semble que les distances seraient finalement mises à jour.

Par exemple:

La revendication est que (A, C) est mis à 1 et jamais mis à jour à la distance correcte -2. Mais le pseudocode de CLRS dit que nous plaçons d'abord C et B sur le tas avec les distances 1 et 2 respectivement; alors nous sautons C, ne voyons pas d'arêtes sortantes; alors nous sautons B, regardons le bord (B, C), voyons que Dist[C] > Dist[B] + w(B,C), mettez Dist[C] à -2, remettez C sur le tas, ne voyez pas de bords sortants et nous avons terminé. Alors ça a bien marché.

Même chose pour l'exemple dans la première réponse à cette question: Negative weights using Dijkstra's Algorithm

L'auteur de la réponse affirme que la distance C ne sera pas mis à jour -200, mais selon ce pseudo-code qui est pas vrai, puisque nous mettrions B revenir sur le tas, puis calculer la distance la plus courte correcte à C.

(pseudocode de CLRS)

Dijkstra(G(V, E, ω), s ∈ V) 
for v in V do 
    dist[v] ← ∞ 
    prev[v] ← nil 
end for 
dist[s] = 0 
H←{(s,0)} 
while H̸=∅ do 
    v ← DeleteMin(H) 
    for (v, w) ∈ E do 
     if dist[w] > dist[v] + ω(v, w) then 
      dist[w] ← dist[v] + ω(v, w) 
      prev[w] ← v 
      Insert((w, dist[w]), H) 
     end if 
    end for 
end while 

EDIT: Je comprends que nous supposons qu'une fois qu'un noeud est sorti du tas, la distance la plus courte a été trouvée; mais encore, il semble (d'après le CLRS) que nous replaçons les nœuds sur le heap si la distance est plus courte que précédemment calculée, donc à la fin quand l'algorithme est fini, nous devrions avoir la bonne distance la plus courte.

Answer 1

Cette implémentation n'est techniquement pas l'algorithme de Dijkstra, qui est décrit par Dijkstra here (impossible de trouver un meilleur lien): l'ensemble A dont il parle sont les nœuds pour lesquels le chemin minimum est connu. Donc, une fois que vous ajoutez un noeud à cet ensemble, il est corrigé. Vous connaissez le chemin minimum et il ne participe plus au reste de l'algorithme. Il parle également de transférer des nœuds, de sorte qu'ils ne peuvent pas être dans deux ensembles à la fois.

Ceci est conforme à la pseudocode de Wikipédia:

1 function Dijkstra(Graph, source): 
2 
3  create vertex set Q 
4 
5  for each vertex v in Graph:    // Initialization 
6   dist[v] ← INFINITY     // Unknown distance from source to v 
7   prev[v] ← UNDEFINED     // Previous node in optimal path from source 
8   add v to Q       // All nodes initially in Q (unvisited nodes) 
9 
10  dist[source] ← 0      // Distance from source to source 
11  
12  while Q is not empty: 
13   u ← vertex in Q with min dist[u] // Node with the least distance will be selected first 
14   remove u from Q 
15   
16   for each neighbor v of u:   // where v is still in Q. 
17    alt ← dist[u] + length(u, v) 
18    if alt < dist[v]:    // A shorter path to v has been found 
19     dist[v] ← alt 
20     prev[v] ← u 
21 
22  return dist[], prev[] 

Et son pseudocode tas aussi bien.

Toutefois, notez que Wikipedia indique également, au moment de cette réponse:

Au lieu de remplir la file d'attente prioritaire avec tous les noeuds dans la phase d'initialisation, il est également possible d'initialiser à contenir seule source ; puis, à l'intérieur si alt < dist [v] bloc, le noeud doit être inséré si pas déjà dans la file d'attente (au lieu d'effectuer une opération de decrease_priority) [3]:. 198

Faire cela serait encore conduire à réinsérer un noeud dans certains cas avec des bords évalués négatifs, tels que le graphe d'exemple donné dans la réponse acceptée au second linked question.

Il semble donc que certains auteurs font cette confusion. Dans ce cas, ils doivent indiquer clairement que cette implémentation fonctionne avec des bords négatifs ou que ce n'est pas une implémentation correcte de Dijkstra.

Je suppose que le document original pourrait être interprété comme un peu vague. Il ne fait nulle part mention de la présence d'arêtes négatives ou positives dans Dijkstra, et il ne précise pas non plus qu'une autre interprétation qu'un nœud ne peut pas être mis à jour une fois dans l'ensemble A. Je ne sais pas s'il a clarifié lui-même les choses dans d'autres travaux ou discours ultérieurs, ou si le reste n'est qu'une question d'interprétation par d'autres.

Donc, de mon point de vue, on pourrait dire que c'est aussi un Dijkstra valide. Pour ce qui est de savoir pourquoi vous pourriez l'implémenter de cette façon: parce que nous n'aurons probablement pas plus de lenteur si nous avons seulement des bords positifs, et parce qu'il est plus rapide d'écrire sans avoir à effectuer de vérifications supplémentaires ou de tas non standard. opérations.