Plus court chemin sur un graphe aux arêtes étiquetées positivement (Dijkstra)

Répertoire GitHub correspondant à cet article : https://github.com/peportier/ia04-dijkstra

Principe de l'algorithme

Nous considérons un graphe dont chaque arête est étiquetée avec un nombre positif ou nul. Il s'agit de calculer pour chaque nœud du graphe sa plus courte distance à un nœud fixé. La plus courte distance entre deux nœuds est la longueur du plus court chemin entre ces deux nœuds.

L'ensemble des nœuds noirs est l'ensemble des nœuds pour lesquels la plus courte distance à a été établie. Un plus court chemin ne visite que des nœuds noirs.

L'ensemble des nœuds gris est l'ensemble des nœuds pour lesquels la longueur d'un chemin y menant depuis a été trouvée, mais cette longueur n'est pas nécessairement minimale. Par contre, c'est la longueur minimale parmi l'ensemble des longueurs des chemins qui n'ont que des nœuds noirs entre et ce nœud gris.

Au sujet des nœuds blancs, nous ne savons rien... sinon que tout chemin considéré depuis jusqu'à un nœud blanc doit d'abord passer par un nœud gris.

On note la distance associée à un nœud noir ou gris. C'est la longueur du chemin le plus court actuellement connu pour rejoindre à partir de . Ce dernier chemin n'est donc fait que de nœuds noirs.

Comment choisir le prochain nœud gris qui deviendra noir ?

Nous montrons que nous pouvons choisir un nœud gris qui minimise .

Considérons un chemin quelconque de à et notons sa longueur . Ce chemin peut contenir d'autres nœuds gris et même des nœuds blancs. Puisque est noir et que est gris, à un moment donné ce chemin quitte la région noire. Soit le premier nœud non-noir (c-à-d gris) de ce chemin. peut être égal à ou ne pas être égal à . Puisque a été choisi pour minimiser , nous avons : . Puisque la distance de à est positive ou nulle, nous avons : . Donc . Donc ce chemin est au moins aussi long que celui dont la découverte avait mené à la mémorisation de la valeur actuelle . Donc la longueur du plus court chemin de à est , et le nœud devient noir.

Tous les successeurs blancs de sont colorés en gris, et une distance est mémorisée pour chacun d'entre eux, faite de la plus courte distance de à ( ) à laquelle on ajoute la distance de à ce successeur.

Tous les successeurs gris de restent gris, mais la distance qui leur est associée peut être réduite (si le chemin qui passe par est plus court).

Pour les successeurs noirs de , il n'y a rien à faire.

Implémentation

La liste d'adjacence d'un noeud contient maintenant les poids des arêtes qui permettent d'atteindre les voisins de ce noeud

 

L'implémentation de l'algorithme suit d'assez près le pseudo-code de notre dérivation. La différence principale réside dans l'utilisation d'une file de priorité, et dans le maintient d'une structure map< node*, node* > parent qui permet de reconstruire le chemin une fois la destination atteinte.

 

Nous testons l'algorithme sur un exemple de graphe étiqueté positivement.

 

Nous trouvons bien le plus court chemin de n1 vers n3.

1
4
1
1
2
1
1
1
2
3
4
5
6