vignette|Exemple d'un plus court chemin du sommet A au sommet F : (A, C, E, D, F). En théorie des graphes, le 'problème de plus court chemin' est le problème algorithmique qui consiste à trouver un chemin d'un sommet à un autre de façon que la somme des poids des arcs de ce chemin soit minimale. Il existe de nombreuses variantes de ce problème suivant que le graphe est fini, orienté ou non, que chaque arc ou arête possède ou non une valeur qui peut être un poids ou une longueur. Un chemin le plus court entre deux nœuds donnés est un chemin qui minimise la somme des valeurs des arcs traversés. Pour calculer un plus court chemin, il existe de nombreux algorithmes, selon la nature des valeurs et des contraintes supplémentaires qui peuvent être imposées. Dans de nombreux cas, il existe des algorithmes de complexité en temps polynomiale, comme l'algorithme de Dijkstra dans des graphes avec poids positifs. En revanche, lorsque des contraintes supplémentaires comme des fenêtres de temps sont ajoutées, le problème peut devenir NP-difficile. L'exemple d'application le plus courant est la recherche d'un trajet le plus court entre deux agglomérations. Ce problème d'apparence facile, puisqu'il s'agit simplement d'additionner les distances kilométriques, devient plus compliqué si on veut en déduire le temps de parcours, car l'intensité du trafic, le temps de traversée des agglomérations, sont des contraintes additionnelles. La recherche de chemin est au contraire un problème d'intelligence artificielle qui se rattache à la planification. Il consiste à trouver comment se déplacer dans un environnement entre un point de départ et un point d'arrivée en prenant en compte différentes contraintes. Il devient ardu lorsque diverses contraintes additionnelles (exécution en temps réel, présence d'incertitudes, contrainte de ressources, environnement évolutif, etc.) doivent être prises en compte. Le problème et ses solutions dépendent d'abord de la nature des poids : chaque arc est doté d'un poids qui est un nombre réel.