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

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.

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.

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.

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,

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

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,

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.

Enfin, nous extrayons B, après quoi . 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,

Donc nous nous retrouvons avec les distances comme

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

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 n'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 n'a pas été considéré, laissant le chemin le plus court actuel inchangé.

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

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.

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.

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:

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.

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.

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.