Combien d'insertions dans la file de priorité ?

Mesure sur le graphe de l'exercice précédent ($n=6$, $m=9$) :

insertions = 8   extractions = 8   extractions ignorees = 2

Huit insertions pour six sommets : les deux surnuméraires sont le $(14,5)$ doublé par $(11,5)$, et le $(22,3)$ doublé par $(20,3)$ — exactement les deux relâchements « perdants » repérés à l'exercice précédent.

La borne exacte. Une insertion a lieu à chaque relâchement réussi, c'est-à-dire à chaque fois qu'un arc $(u,v)$ améliore $d[v]$. Chaque arc n'est examiné qu'une fois — lorsque son origine $u$ est figée — et ne peut donc provoquer qu'une insertion au plus. Avec la source, cela donne

$$\text{insertions}\le m+1,$$

et le même compte pour les extractions. La complexité est donc $O((n+m)\log (n+m))$, que l'on écrit $O((n+m)\log n)$ puisque $m\le n^2$ et donc $\log m\le 2\log n$.

Pourquoi on préfère les doublons à la modification de priorité. Un tas binaire (chapitre chap:tas) ne sait pas diminuer la clé d'un élément qu'il contient : il faudrait savoir où il se trouve, donc maintenir un index sommet $\to$ position et le mettre à jour à chaque échange du tas. C'est faisable, cela ramène la file à $n$ éléments — et cela coûte une structure de plus, un invariant de plus, et une source de fautes de plus. Le doublon échange de la mémoire contre de la simplicité, et c'est presque toujours le bon échange.

Et ce que la garde protège. Sans le if not fige.(u), l'extraction redondante de $5$ (avec l'estimation périmée $14$) relâcherait à nouveau ses arcs, à partir d'une valeur fausse. Les distances resteraient correctes — un relâchement ne peut qu'améliorer — mais le nombre d'insertions cesserait d'être borné par $m$ : chaque doublon en engendrerait d'autres. La garde n'est pas là pour la correction, elle est là pour la complexité, ce qui est précisément le contraire de la garde de Boyer-Moore du chapitre chap:textes.