Plus court chemin

Soit $g$ un graphe orienté (ou non) muni d'une valuation de arêtes $c$. Un chemin $C$ de longueur $p$ dans $G$ est un $p$-uplet $(c_1, \ldots, c_p)$ d'éléments de $A$ tel que si $c_i = (s_i, t_i)$, alors pour tout $i \in \{1, \ldots, p - 1\}$, $t_i = s_{i+1}$. $C$ est un chemin de $u \in S$ à $v \in S$ si $s_1 = u$ et $t_p = v$.

Le problème du plus court chemin dans un graphe valué se définit comme suit :

• données : un graphe $G$ valué, deux sommets $u$ et $v$
• question : trouver le plus court chemin de $u$ à $v$ dans $G$.

Ce problème est polynomial, Les deux algorithmes les plus connus sont

• Dijkstra : très rapide, $\mathcal{O}(\vert S\vert + \vert A\vert)$ dans le pire des cas, mais ne fonctionne qu'avec les valuations positives, ne nécessite pas le parcours de tout le graphe.
• Bellman : un peu moins rapide, il présente l'avantage de fonctionner avec des valuations négatives, sauf si le graphe contient un circuit absorbant (i.e. négatif).