Plus Court Chemin : shortest path.
Trouver le chemin le moins coûteux dans un graphe (connexe évidemment).
Le coût d'un chemin est généralement exprimé en termes de longueur/distance, mais pas forcément (on peut le remplacer par le temps de parcours) ou seulement (on pourra ajouter une densité de traffic par exemple). Le problème peut également être corsé en rajoutant des contraintes de temps : coût dynamique (variant selon le moment), passage possible qu'à certains moments, etc.
Les méthodes pour trouver le PCC sont généralement des algorithmes gloutons qui supposent le principe d'optimalité de Bellman (1955), qui considère que, si un chemin est optimal, un sous-chemin de ce chemin optimal est également optimal pour arriver à cette étape intermédiaire. Cette supposition permet de trouver le bon chemin progressivement, par une résolution ascendante (résolution à partir de sous-solutions) n1Voir aussi le 3ᵉ précepte de la méthode de Descartes.
Il existe plusieurs méthodes de résolution du problème, plus ou moins adaptés en fonction du contexte :