Graphe acyclique

Lorsqu'un graphe ne comporte pas de circuit, les arcs traduisent une relation d'ordre partiel sur le graphe. Ce qui veut dire que l'on peut numéroter les sommets de $G$ de telle manière que $(\ivj)\:\in\:G\: \Rightarrow \: i \, < \, j$. Une telle numérotation s'appelle un tri topologique sur $G$. Le calcul d'un tri topologique (ou ordre topologique) sur un réseau se fait par un algorithme de complexité maximale en $O(m)$. Dès lors qu'il existe un circuit sur le graphe, il devient impossible de créer un tel ordre car tout sommet membre d'un circuit est l'un de ses propres prédécesseurs. L'algorithme suivant permet de déterminer un ordre topologique sur un graphe.

Le principe de cet algorithme est simple et repose sur l'élimination progressive des arcs sortant de chaque sommet. Nous utilisons les variables $\delta(i)$ indiquant à chaque instant, combien d'arcs non encore biffés du réseau entrent dans le sommet $i$. Initialement, $\delta(i) \: = \: \vert\omega^-(i)\vert$, $\forall \:i\:\in\: X$ et la liste contient l'ensemble des sommets qui n'ont pas de prédécesseurs et qui sont donc directement numérotables. A chaque fois que l'on examine un sommet, on coupe les arcs qui en sortent et on place dans la liste les sommets qui n'ont plus d'arc entrant. Ainsi, on est sûr d'examiner tous les prédécesseurs d'un sommet avant de le numéroter. Une fois cet ordre topologique connu, le calcul des plus courts chemins est très simple. En effet, supposons que l'on cherche à calculer $d(k)$ et que l'on connaisse les plus courtes distances pour tous les sommets de rang topologique inférieur à celui de $k$. De par la définition de l'ordre topologique, tous les arcs arrivant en $k$ proviennent de sommets de rang inférieur, c'est-à-dire de sommets pour lesquels on connaît déjà les plus courtes distances (de par l'hypothèse). Alors, pour connaître $d(k)$ (et, par la même occasion, un plus court chemin joignant $s$ à $k$), il suffit de considérer :

$$\begin{array}{lcl} j &=& \arg \min\limits_{i:(i,\,k)\in G}... ...d(k)&=& d(j)\:+\:c_{jk} \\ \text{pred}[k]&=&j \end{array}$$

où $j$ est le sommet prédécesseur de $k$ de distance minimale par rapport à $s$. On obtient alors l'algorithme suivant initialisé en $s$, seul sommet sans prédécesseur par définition.