Sommaire

Algorithmes "intelligents"

Les parcours en profondeur et en largeur ne permettent pas de trouver le chemin le plus court, mais juste le premier qui permet de joindre le point de départ au point d’arrivée.

D’autres algorithmes existent, qui permettent de déterminer le chemin le plus court, ou au moins un chemin optimisé, et ce sans forcément avoir à tester tous les chemins possibles.

1. Algorithme de Bellman-Ford

L’algorithme de Bellman-Ford permet de trouver le chemin le plus court s’il existe. Il n’est pas le plus optimisé, mais c’est celui qui fonctionne dans le plus de cas. En effet, il accepte des longueurs négatives pour les arcs, et pas seulement des positives.

De plus, s’il y a un circuit dont la longueur est négative (et donc qui permet de diminuer le poids total), il peut le détecter. C’est important, car dans ce cas-là il n’existe pas de chemin le plus court.

a. Principe et pseudo-code

Cet algorithme va utiliser la matrice des longueurs. Son fonctionnement est itératif.

Au départ, on initialise à + la longueur minimale de chaque nœud (ce qui signifie que l’on n’a pas encore trouvé de chemin jusque-là depuis l’arrivée). On va aussi garder pour chaque nœud le nœud précédent (celui qui permet d’y arriver avec la plus faible longueur) et l’initialiser au nœud vide.

On applique ensuite autant de fois que le nombre ...