Problème du Plus Court Chemin

Présentation

Lorsque vous vous déplacez d'un endroit à un autre, vous préférez généralement y arriver le plus rapidement possible. De nos jours, on utilise des logiciels capables de calculer un chemin optimal en un temps minime. Ce problème a pour application évidente les logiciels de géolocalisation, mais il concerne également d'autres domaines, tels que le routage dans le réseau Internet ou même dans le jeu vidéo sous le terme plus répandu de Pathfinding.

Pour mieux illustrer ce problème, nous aiderons Mathman le chevalier masqué à arriver le plus rapidement possible au Mathsignal pour appréhender les criminels de Gomath City.

I. Formalisation

On peut représenter La ville de Gomath City à l'aide d'un graphe G = (S, A) tel que A un ensemble d'arêtes représentant les rues et S un ensemble de sommets représentant les intersections.

II. Contraintes

Les rue de Gomath City ne sont pas à doubles sens, aussi elles possèdent toutes des limitations de vitesse différentes. Ainsi, Mathman, symbole de la justice et de la rigueur mathématique ne transgresse pas ces règles. Même pour rejoindre le Mathsignal au plus vite.

Ces contraintes correspondent à celles d'un graphe orienté et valué. Un graphe orienté étant un graphe ou les arêtes possèdent un sens de parcours définit, et un graphe valué est un graphe ou les arrètes ont un poids. Les rues de Gomaths ne pouvant faire remonter dans le temps il n'y aurait aucun sens à trouver des poids négatifs dans notre graphe, bien que cela ne soit théoriquement pas impossible.

Ci-dessus un exemple de graphe orienté et valué

III. Un algorithme: Dijkstra

Il existe plusieurs algorithmes pour résoudre le problème du plus court chemin. Dans notre cas c'est celui de Dijkstra qui est le plus intéressant. Il s'agit aussi du plus régulièrement utilisé dans des cas similaires.

Le principe de cet algorithme est l'utilisation d'une file de priorité. En bref, il s'agit d'une liste où sont rangés les sommets du graphe ainsi que le poids calculé jusque là par l'algorithme. L'idée est que l'on supprime le poids le plus faible de la liste car il s'agit du chemin minimum pour atteindre ce sommet, puis d'effectuer une itération à partir de se sommet.

Soit u, v deux sommets tels que u est extrait à l'itération i et v est extrait à l'itération i+1. A la première itération on extrait s et d[s] = 0. Donc vrai au premier rang. On distingue deux cas:

  • Si d(i)[v] = d(i+1)[v]. Alors vrais car u extrait avant donc d(i)[u] <= d(i)[v] = d(i+1)[v]
  • Si le poids w(u,v) >= 0 alors d[v] = d[u] + w(u, v). Donc d[u] <= d[v]

Déroulement de Dijkstra

O. Graphe Initial.

Le tableau V représentes les poids des chemins vers chaque sommets et le Tableau P représentes les prédécesseures.

I. Première Itération.

On parcours les successeurs de 1. V[2] prend donc la valeur du poids de l'arête (1, 2) et P[2] prend la valeur de 1 son prédécesseur.
De même pour le sommet 4.

II. Seconde Itération

On réitère cette fois pour le sommet 2.

III. Troisième Itération

Pour l'itération au sommet 3, on se rend compte que le poids calculé pour atteindre 4 en passant par les sommet 2 et 3 est plus court que celui calculé précédemment. On remplace dont V[4] par le nouveau poids, et on met a jours son successeur.
Rien de particulier pour cette étape. 5 n'ayant pas encore été atteint jusque là.

IV. Quatrième Itération

Ici le poids pour atteindre 2 à partir de 4 est de 6 là ou V[2] = 1. On ne fait donc aucune modification.
Comme pour M[4] à l'itération III le poids pour atteindre 5 en passent par 4 est plus court. On met donc à jours les tableaux V et P.

Sources Images: https://www.pairform.fr/doc/1/32/180/web/co/Dijkstra.html

La complexité de l'algorithme s'évalue en O(A*log(S)). Où A est le nombre d'arêtes du graphe et S son nombre de sommet. Car il y a maximum S extractions dans la file, d'où log(S). Ainsi que A mises à jour de cette même file d'où A*.

En cas d'arêtes de poids négatif ou nul

Comme dit plus haut, notre modélisation prend en comptes les rues d'une ville. Il n'y aurait donc aucune logique à avoir des arêtes de poids inférieur ou égal à 0. Pourtant c'est un cas que l'on peut rencontrer en mathématiques.

L'algorithme de Dijkstra, bien que très efficace, ne fonctionne pas dans le cas d'arêtes de poids négatif ou nul. C'est pour cela qu'il existe les algorithmes A* et Bellman-Ford. Nous présenterons succinctement seulement ces deux algorithmes car ils ne sont pas nécessaires à notre modélisation.

Bellman-Ford

L'algorithme de Bellman-Ford est très utilisé en informatique, et, comme dit précédemment, il nous permet d'appréhender le cas où on a des chemins à valeur négative. Cet algorithme utilise le principe de la programmation dynamique (méthode algorithmique très utilisée de nos jours qui consiste à décomposer un problème en sous-problèmes) et de la relaxation similairement à Dijkstra (terme anglais définissant les méthodes itératives).

L'algorithme retourne les distances d'un sommet source donné à tous les autres sommets, et ce S-1 fois, où S est le nombre de sommets. A chacune de ces répétitions, le nombre de sommets dont la distance a été calculée augmente, jusqu'à ce que chaque sommet ait sa distance à notre origine calculée. C'est cette distinction avec l'algorithme de Dijkstra, qui lui utilise une file de priorités, qui permet à Bellman-Ford d'être appliqué dans une plus grande variété de cas.

Un pseudo-code de cet algorithme va comme suit :

fonction Bellman_Ford(G, s) 
   pour chaque sommet u du graphe
   |        d[u] = +∞
   d[s] = 0

   pour k = 1 jusqu'à Nombre de sommets - 1 faire
    |    pour chaque arc (u, t) du graphe faire
    |      |    d[t] := min(d[t], d[u] + poids(u, t))

   retourner d

//Preuve de Bellman-Ford

La complexité de cet algorithme est en O(S*A) où S est le nombre de sommets, et A le nombre d'arêtes.

A*

L'algorithme A* permet lui aussi de prendre en compte un des cas que l'algorithme de Dijkstra n'appréhende pas : celui des arêtes à poids nul. Il est assez populaire en informatique, et est souvent vu comme une extension de l'algorithme de Dijkstra.

À chaque itération de sa boucle principale, A* doit déterminer lequel de ses chemins il doit étendre. Il procède en fonction du coût du chemin, et d'une estimation du coût requis pour étendre ledit chemin jusqu'à l'objectif d'arrivée. Spécifiquement, A* sélectionne le chemin qui minimise f(n) = g(n) + h(n) Où n est le prochain noeud, g(n) est le coût du chemin de l'origine à n, et h(n) est une fonction heuristique qui estime le coût du chemin le moins coûteux à partir de n.

A* se termine lorsque le le chemin qu'il choisir d'étendre est un chemin de l'origine à l'arrivée, ou qu'il n'y a plus nulle part où s'étendre. La fonction heuristique évolue selon le problème. Si la fonction heuristique est valide, A* est lui aussi valide. À chaque itération de sa boucle principale, A* doit déterminer lequel de ses chemins il doit étendre. Il procède en fonction du coût du chemin, et d'une estimation du coût requis pour étendre ledit chemin jusqu'à l'objectif d'arrivée.

Spécifiquement, A* sélectionne le chemin qui minimise f(n) = g(n) + h(n) Où n est le prochain noeud, g(n) est le coût du chemin de l'origine à n, et h(n) est une fonction heuristique qui estime le coût du chemin le moins coûteux à partir de n. A* se termine lorsque le le chemin qu'il choisir d'étendre est un chemin de l'origine à l'arrivée, ou qu'il n'y a plus nulle part où s'étendre. La fonction heuristique évolue selon le problème. Si la fonction heuristique est valide, A* est lui aussi valide

Et Enfin: Floyd-Warshall

Pour finir, nous présentons l'algorithme de Floyd-Warshall. L'intérêt de cet algorithme est que contrairement aux autres que calculaient les plus courts chemins à partir d'un sommet donné, il calcule l'intégralité des plus courts chemins entres chaque sommets du graphe.

L'idée de cet algorithme est remplir une matrice représentent le graphe valué sur lequel on travail. Dans cette matrice on stockera le poids des chemin entre chaque sommets. Cette matrice se comprend comme un tableau a deux entrées. Il s'agit d'un algorithme s'évaluant en O(n^3).

Déroulement de Floyd-Warshall

O. Graphe Initial

Pour initialiser les matrices M et P on regarde s'il existe un arc ou non entre les deux sommets. On insert le poids et le prédécesseur s'il y à un arc. On insert un poids infini et un prédécesseur 0 s'il n'y en à pas.

I. Première Itération

On met à jour les matrices si un chemin plus court est trouvé.
Si un chemin arrivant à un sommet déjà vu n'est pas plus court, on ne fait pas de mise à jour.

II. Deuxième Itération

Toujours là même idée ici.
Et encore là.

III. Troisième Itération

Ici on trouve un chemin plus court pour (2, 1), on fait donc une mise à jour.
Idem ici. Le nouveau chemin de 4 vers 1 est plus court que le précédent.

Sources Images: https://www.pairform.fr/doc/1/32/180/web/co/Dijkstra.html

Conclusion

Nous avons donc vu quatre algorithmes dont deux applicables dans notre modèle.
Le premier, Dijkstra, nous à permis de trouver le plus court chemin à partir d'un sommet donné de façon très efficace. Le second, Floyd-Warshall, nous à permis de trouver tout les plus courts chemins entre chaque sommet d'un graphe. Donc, si Mathman souhaite connaître le plus court chemin entre lu et le math signale, il devrait implémenter l'algorithme de Dijkstra dans le Mathordinateur, car ce-dernier semble plus adapté pour son problème.


1 Cliquer pour recommander cet article