Prouver que les valeurs de distance extraites dans l'algorithme de Dijkstra ne sont pas décroissantes?

Question

Je revois mes anciennes notes d'algorithmes et j'ai trouvé cette preuve. C'était d'une mission que j'avais et je l'ai eu raison, mais je pense que la preuve manque certainement.

La question est de prove that the distance values taken from the priority queue in Dijkstra's algorithm is a non-decreasing sequence.

Ma preuve est la suivante:

Preuve par contradiction. Fist, supposons que nous tirons un sommet de Q avec d-value 'i'. La prochaine fois, nous tirerons un sommet avec la valeur d '' j '. Lorsque nous tiré i, nous avons finalisé notre valeur d et calculé le chemin le plus court du sommet de départ, s, à i. Depuis nous avons des poids de bord positifs, il est impossible pour nos valeurs de D pour réduire comme nous ajoutons des vertices à notre chemin. Si après avoir tiré je de Q, nous tirons j avec une valeur d plus petite, nous ne pouvons pas avoir un chemin le plus court vers moi, car nous pouvons être capable d'atteindre i à j. Cependant, nous avons déjà calculé le chemin le plus court à i. Nous n'avons pas vérifié un chemin possible . Nous n'avons plus de chemin garanti . Contradiction.

Comment cette preuve peut-elle être améliorée? Ou mieux encore, y a-t-il une approche différente? Il semble juste assez faible :)

Edit: Désolé, dans ce cas, ma file d'attente prioritaire est mise en œuvre avec un mini-tas

Answer 1

Établissons ces (ceux-ci sont tout à fait vrai, car ils sont, au fond, la définition de l'algorithme):

1. la file d'attente prioritaire dans l'algorithme de Dijkstra vous donnera le nœud le plus bas d-valeur dans chaque itération de l'algorithme.
2. Il n'y a pas de poids de bord négatif.
3. Une fois qu'un noeud a été retiré, il ne retournera jamais dans la file d'attente.
4. La valeur d d'un noeud qui a été retiré est définitive et ne changera pas à partir de ce point.

continue (1), la valeur D de ce noeud dequeued, en supposant que (2) est applicable, sera au moins égale à la précédente valeur d d'extraction, étant donné que d-valeur de chaque noeud dépend sur les d-valeurs des nœuds dequeued avant lui, qui est une sorte de définition récursive. Puisque (3) et (4) sont corrects, cette définition récursive se termine au nœud de départ qui a la valeur d de 0.
Donc, si la valeur d de chaque nœud est au moins égale à la valeur d devant lui , et (1) s'applique toujours, l'ensemble des valeurs d extraites de la file d'attente prioritaire est non décroissant.

(Après avoir lu cela, et ce que vous avez écrit, il est fondamentalement la même, mais a présenté un peu mieux je pense)