La sous-structure optimale en défaut, sur un exemple de cinq arêtes

Quatre sommets, cinq arêtes non orientées : $0-1$, $1-2$, $2-3$, $3-0$ et $1-3$.

Énumération complète des chemins simples (aucun sommet répété), longueur en nombre d'arêtes :

plus long chemin simple 0 -> 2 : 3 aretes, 0-1-3-2  (et 0-3-1-2)
plus long chemin simple 0 -> 1 : 3 aretes, 0-3-2-1

Ce qui casse. Le plus long chemin simple de $0$ à $2$ est $0-1-3-2$. Son préfixe de $0$ à $1$ est le chemin $0-1$, de longueur $1$. Or le plus long chemin simple de $0$ à $1$ est $0-3-2-1$, de longueur $3$. Un sous-chemin d'un plus long chemin simple n'est donc pas un plus long chemin simple : la sous-structure optimale est en défaut, et sur quatre sommets.

Pire : on ne peut pas non plus recoller. Le plus long $0\to 1$ ($0-3-2-1$) et le plus long $1\to 2$ ($1-0-3-2$) ne se composent pas — leur concaténation repasse par $0$, $2$ et $3$, et n'est plus un chemin simple.

La leçon, et elle est générale. La contrainte « simple » est globale : elle porte sur le chemin entier, pas sur ses morceaux. Or la programmation dynamique suppose que le sous-problème se pose indépendamment du reste. C'est cette indépendance qui manque, et c'est pourquoi aucune récurrence sur « le plus long chemin de $u$ à $v$ » ne peut être correcte. Pour la rendre correcte, il faudrait mettre l'ensemble des sommets déjà visités dans l'état — ce qui donne $2^n$ sous-problèmes, et c'est exactement l'idée du dernier problème de ce chapitre, sur le voyageur de commerce. La sous-structure ne s'obtient qu'en payant l'exponentielle.

Pour les plus courts chemins, au contraire, aucune contrainte globale n'intervient : un sous-chemin d'un plus court chemin est un plus court chemin (chapitre chap:parcours), et tout fonctionne.