Le problème du plus court chemin est un problème algorithmique qui consiste à trouver dans un graphe un chemin d’un sommet de départ à un sommet de destination de façon que la somme du poids des arcs constituant le chemin soit minimale.
Il existe différentes variantes de ce problème suivant que le graphe soit fini, orienté ou non et que chaque arc possède une valeur ou non. Il existe de nombreux algorithmes pour calculer le plus court chemin tel :
– L’algorithme de Dijkstra pour des graphes dont les poids sont positifs.
-L’algorithme de Floyd pour les graphes orientés.
-L’algorithme de A* qui a comme très grand avantage d’être très économes en ressource et qui est donc particulièrement adapté dans un usage informatique.
Cependant il existe des cas de figure ou d’autres contrainte doivent être prisent en compte en plus du poids des arcs comme par exemple dans un graphe ou les sommets représentes des villes, en plus de la contrainte liée au poids des arcs représenté ici par la distance séparent des villes, d’autre élément pourrait être ajoutés comme une contrainte de temps, d’essence ou encore d’embouteillage sur certain chemin. Cet exemple complexe ne peut pas être résolu par un simple algorithme de manière optimal mais pas une intelligence artificielle.
Graphes et Algorithmes 