L'algorithme de diksta... dijstrak... DIJKSTRA !

Ce weekend j'avais envie de programmer un peu. Un truc nouveau (du moins pour moi), que je ne connais pas trop, et pas forcément très utile. Mon choix s'est porté sur l'implémentation de l'algorithme de Dijkstra permettant de rechercher quel est le plus court chemin entre deux nœuds dans un graphe. C'est un algorithme utilisé en autre par le protocole de routage dynamique OSPF (où chaque nœud est un routeur et chaque arc une liaison).

L'algorithme de Dijkstra permet d'attribuer à chaque arc du graph un poids. Le chemin le plus court n'est dont pas déterminé par le nombre de nœuds qui séparent ceux de départ et d'arrivée, mais par le poids des arcs. Par exemple, pour le graphe ci-dessous, pour aller de A à F, l'algorithme de Dijkstra prendra le chemin qui passe par A, C, D, E, F même si celui-ci traverse plus de nœuds.

Mon implémentation du Dijkstra est appliquée au réseau du métro de Paris, chaque station étant un nœud et le chemin entre deux un arc. Le but est donc de rechercher le plus court chemin entre deux stations. Bien entendu, je ne cherche pas à concurrencer l'outil du site de la RATP pour calculer les itinéraires, ces derniers ayant accès à bien plus de facteurs que moi pour leur calcul (comme la durée de voyage entre deux stations, les éventuels incidents en cours, l'heure et la fréquence des trains sur les lignes, le temps de marche entre les correspondances etc.). Le but est juste de mettre en pratique l'algorithme.

Avant de continuer sur mon implémentation, je vais expliquer rapidement et en images comment fonctionne le Dijkstra.

La première phase est une sorte d'initialisation où l'on va compter la valeur des poids qui séparent deux nœuds en gardant la valeur la plus faible (en cas de chemins multiples) et en partant du nœud de départ. Pour cela, ajouter deux attributs à un nœud : son prédécesseur et la somme du chemin le plus court vers le nœud de départ.

La première chose à faire sera d'initialiser ces valeurs. Le point de départ aura une somme de chemin parcouru égale à zéro, et les autre à l'infini. Aucun n'aura de prédécesseur.

On va ensuite passer par chaque nœud, mais dans un ordre particulier : en prenant à chaque fois celui qui à le chemin parcouru le plus court.

Pour chaque nœud (appelons le N1), on prends tous les autres nœuds qui lui sont connecté. Et pour chacun de ces nœuds (appelons les N2), on regarde si le chemin parcouru par N2 est supérieur à la somme du chemin parcouru par N1 et le poids de l'arc qui sépare les deux. Si c'est le cas, on définit la somme des chemins parcourus par N2 à la somme du chemins parcouru par N1 + la valeur du poids de l'arc, ainsi que le prédécesseur de N2 à N1.

Au final, on se retrouve avec un graphe dont chaque nœud possède un prédécesseur qui est le chemin le plus court vers le nœud de départ.

La seconde phase consiste à récupérer le chemin à parcourir pour aller du nœud d'arrivée au nœud de départ. Il suffit de prendre le prédécesseur du nœud d'arrivée, puis le prédécesseur de ce prédécesseur, puis le prédécesseur du prédécesseur du prédécesseur... Pour enfin arriver au nœud de départ. A chaque fois, on stocke le nœud en cours au début d'une liste (par exemple), et au final la liste contiendra la liste de nœud à passer pour aller du départ à l'arrivée.

Dans mon cas (celui du métro pour ceux qui ne suivent pas), j'avais un autre facteur important à traiter : les lignes et par extension, les correspondances. Il faut en premier lieu savoir dans quel ligne est parcouru un nœud, car il faudra au final, lorsque l'on synthétise le trajet pouvoir indiquer à l'utilisateur les changements à faire. En second lieu, imposer un malus dans le poids lorsque l'on change de ligne.

J'ai donc ajouté un attribut aux arcs : la ligne (de métro) qu'ils représentent. Ensuite, lors du calcul des chemins parcourus, pour chaque arc entre chaque nœud N2 qui est relié à chaque nœud N1, je regarde si un changement de ligne sera effectué au passage de N1 à N2, et ajoute un malus de correspondance au poids si cela est vrai.

Exemple d'exécution :

naps@leon ~/D/l/path> python metro.py
Bienvenue dans le programme de calcul d'itinéraires
 
Entrez une station de départ
>lib
Station Liberté selectionnée pour le départ.
 
Entrez une station d'arrivée
>villette
Station Porte de la Villette selectionnée pour l'arrivée.
 
Itinéraire :
============
 
 - Entrez dans la station Liberté et prenez le métro (sans blague)
 - Changez à République et prendre la ligne 5
 - Changez à Stalingrad et prendre la ligne 7
 - Arrivée à Porte de la Villette (trop bien \\o)

Pour terminer, le code est disponible sur mon Gist, pour Python 2.6 (mon premier 1!), et le fichier décrivant la liste des stations est au même endroit, plus bas dans la page. Je n'ai pas pris la peine de le commenter, le code n'est surement pas optimisé au mieux, et est donc un peu crado sur les bords, mais ceux que ça intéresse pourront, je l'espère, le ré-implémenter avec mes explications ci-haut.