Réalisation d’une application modélisant l’algorithme
DIJKSTRA, sous la plateforme C# .net
Introduction:
Présentant
de grands avantages de rapidité, cet algorithme ne permet que la recherche des
chemins de longueur minimale et pour des graphes pondérés par des poids
positifs.
Cet
algorithme, autorisant la recherche d’un chemin minimal entre deux sommets I (initial)
et F (final). se décompose en quatre phases, comme suit :
Le
principe est le suivant : on affecte provisoirement le poids maximal (+ ∞) à
tous les sommets, sauf pour le sommet initial de poids 0 et ses successeurs
(recevant le poids de l’arc les reliant à I) ; tant que c’est possible, on
diminue les poids provisoires qui deviennent définitifs (un sommet affecté d’un
poids définitif est dit marqué) lorsque leur diminution devient impossible.
Remarque :
Il
se peut que l’algorithme se termine avant que tous les sommets ne soient
marqués (cf. l’alternative du début de la phase 3) ; cela voudra dire qu’aucun
des chemins passant par ces sommets non marqués ne sera un chemin de longueur
minimale.
Exemple :
Cherchons dans le graphe G
ci-dessous, un chemin minimal de I à F, en utilisant l’algorithme de
DIJKSTRA-MOORE, ce qui est possible les poids étant tous positifs.
Dans
la dernière colonne ( Σ ), on a indiqué successivement l’entrée des sommets.
Pour retrouver un chemin minimal, on lit le tableau de droite à gauche. Le
dernier sommet entré est le sommet final F : dans la colonne F, est indiqué
(toujours en dernière position) le poids définitif attribué à F, qui est aussi
la longueur minimale du chemin et qui vaut ici 23. De plus, le prédécesseur de
F qui a contribué à donner son poids à F, est P : on lit dans la colonne P que
le prédécesseur (ayant contribué à donner son poids définitif à P) est L. Puis
la colonne L va nous donner le prédécesseur qui est E ; la colonne E nous donne
ensuite D, la colonne D nous donne B, celle de B nous donne A et celle de A
nous donne I. Le chemin de longueur minimale reliant I à F est donc : [I, A, B,
D, E, L, P, F] et sa longueur est 23.
Remarque :
La
présence de circuits dans le graphe G interdit son partage en niveau et donc l’utilisation
de la version présentée de l’algorithme de FORD. De même, la recherche d’un chemin
de longueur maximale, n’a aucun sens.
Interfaces de l'application:
L'application permet de dessiner
différents points via des coordonnées (x,y), et permet de les relier tout en
donnant une valeur équivalente à chaque arc. Ainsi, On obtient un graphe sur la
carte de la forme principale. Ceci sera bien illustré dans les captures d'écran suivantes représentant les différentes étapes
de la mise en œuvre de l’application :
Après l’insertion de tous les points et arcs, on obtient un graphe :
Ensuite l’utilisateur sélectionne le
point de départ et celui de l’arrivée, l’application applique alors
l’algorithme du Dijkstra et visualise le chemin de coût minimal en rouge, tout
en mentionnant le coût minimal au niveau de chaque point de passage :
N.B :
L’application permet d’enregistrer les graphes sous format <xml> et de
les réouvrir, afin d’éviter les efforts inutiles.