L'algorithme de Dijkstra avec des arêtes négatives sur un graphe orienté

Que si le seul point négatif de bord de coûts sont à venir à partir du nœud initial? Va l'algorithme fonctionne encore?

Je sens que oui, parce que je ne peux pas penser à une contre-exemple, mais je vais avoir de la difficulté à le prouver. Est-il un contre-exemple?

Négatif bords sont un problème pour les Dijkstra est parce qu'il n'y a aucune garantie que le bord, vous choisissez produit le plus court chemin si il existe une arête, vous pouvez choisir plus tard, c'est en grande partie un coefficient de pondération négatif. Mais si le seul point négatif bords sont en sortant du nœud initial, je ne vois pas le problème.

Je ne suis pas à la recherche d'un algorithme. Je suis à la recherche pour un aperçu de la Dijkstra.

Je parle d'un graphe orienté, si cela fait une différence.

source d'informationauteur user438293456

  1. 12

    Contre-exemple:

    Graphe G = (V, E), de sommets V = {A, B}, arêtes E = {(A, B), (B, A)} et la fonction de poids w(A, B) = -2, w(B, A) = +1.

    Il y a un cycle de poids négatif, d'où les distances minimales ne sont pas définis (même en utilisant Un comme nœud initial).

  2. 21

    Le problème avec le fait d'avoir un négatif-coût de bord, c'est que vous pouvez aller et venir le long de autant de fois que vous le souhaitez.

    Si vous imposer une règle à ce que la lame ne peut pas être utilisé plus d'une fois, vous avez toujours un problème. L'algorithme de Dijkstra implique le marquage d'un nœud comme "visité", quand c'est la distance à partir du nœud initial est considéré comme le savoir une fois pour toutes. Ce qui se passe avant toutes les arêtes ont été examinés; le chemin le plus court à partir de la première nœud à nœud X a été trouvé, tous les autres chemins d'accès du nœud initial sont déjà plus que cela, rien de ce qui est découvert par la suite peut prendre ces chemins plus courte. Mais si il y a de négatif de coût bords quelque part, puis plus tard la découverte peut faire un chemin plus court, donc c'est peut être qu'un plus court chemin d'accès n'existe qui Dijkstra ne sera pas découvrir.

    Si les bords se connecter au nœud initial peut avoir des coûts négatifs, alors vous avez encore un problème, parce que le plus court chemin d'accès peut impliquer de revoir le nœud initial pour profiter des coûts négatifs, quelque chose de Dijkstra ne peut pas faire.

    Si vous imposez des un autre règle qu'un nœud ne peut pas être visité plus d'une fois, alors l'algorithme de Dijkstra œuvres. Remarquez que dans l'algorithme de Dijkstra, le nœud initial est donné une distance initiale de zéro. Si vous donnez à une autre distance initiale, l'algorithme va encore trouver le chemin le plus court-- mais toutes les distances seront par la même quantité. (Si vous voulez la distance réelle à la fin, vous devez soustraire la valeur que vous mettez dans.)

    1. Afin de prendre votre graphique, de l'appeler Atrouver le plus petit coût de tout bord connecté au nœud initial, l'appeler k qui sera négatif dans ce cas).
    2. Faire un nouveau graphe B que vous pouvez obtenir en soustrayant k à partir du coût de chaque bord connecté au nœud initial. Noter que la totalité de ces coûts sont maintenant non-négatif. Afin de Dijkstra fonctionne sur B. Notez également que le chemin le plus court dans B est aussi le chemin le plus court dans A.
    3. Attribuer le nœud initial de B la distance de k, puis exécutez Dijkstra (cela donnera le même chemin que l'exécutant avec une distance initiale de zéro). Comparez cela à l'exécution de Dijkstra naïvement sur A: une fois que vous quittez le nœud initial tout est la même dans les deux graphiques. Les distances sont les mêmes, les décisions sont les mêmes, les deux vont produire le même chemin. Et dans le cas de A la distace sera correct, puisqu'il a commencé à zéro.
  3. 0

    De l'algorithme de Dijkstra ne produit pas de réponse correcte pour graphique avec un bord négatif de poids (même si le graphique ne possède pas de cycle de poids négatif). Pour exemple, il calcule incorrect chemin le plus court de la valeur entre (A, C) pour le graphique de la page suivante avec la source de sommet A,

    A -> B : 6
A -> C : 5
B -> D : 2
B -> E : 1
D -> E : -5
E -> C : -2