Recherche de chemins

a. Principe et pseudo-code

Son fonctionnement est assez simple.

Tout d’abord, on choisit l’ordre des parcours de nœuds puis on applique cet ordre pour avancer un maximum. Si on est bloqué, on retourne en arrière, et on teste la deuxième possibilité.

Le parcours en profondeur permet donc de déterminer l’existence d’un chemin, mais il ne prend pas en compte les longueurs des arcs, et donc ne permet pas de dire si l’on a trouvé le chemin le plus court.

De plus, le résultat obtenu dépend fortement de l’ordre choisi pour le parcours du graphe, l’ordre optimal dépendant du problème et ne pouvant être déterminé a priori. Bien souvent, il n’est donc pas efficace. Dans le pire des cas, il doit même tester toutes les possibilités pour trouver un chemin.

Il est cependant facile à implémenter. En effet, nous allons conserver une liste des nœuds visités. À chaque fois que l’on se trouve sur un nœud, nous allons ajouter tous ses voisins non visités à une pile dans l’ordre choisi. Ensuite, nous dépilons le premier élément de celui-ci.

Pour faciliter la reconstruction du chemin obtenu, le prédécesseur de chaque nœud (c’est-à-dire le nœud nous ayant permis d’y aller) est conservé.

Le pseudo-code est donc le suivant :

// Initialisation du tableau 
Créer tableau Precurseur 
Pour chaque noeud n 
    Precurseur[n]...

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 de nœuds moins 1 la même boucle. Ainsi, s’il y a 7 nœuds, on l’applique 6 fois.

À chaque itération, on suit chaque arc (u,v). On calcule la distance depuis le point de départ à v comme étant la distance du départ à u, plus la longueur de l’arc (u,v). On obtient ainsi une nouvelle longueur pour aller au nœud v que l’on compare à celle déjà enregistrée. Si cette longueur est plus faible que celle obtenue jusqu’ici, alors on change la longueur de ce nœud et on indique que son prédécesseur est maintenant u.

Si à une itération il n’y a plus de changement, car aucun arc ne permet de trouver une distance plus faible que celle connue, on peut arrêter prématurément l’algorithme.

De plus, si on applique l’algorithme autant de fois que le nombre de nœuds du graphe, et qu’une modification des poids se fait encore, alors on sait qu’il existe un circuit de taille négative...

a. Implémentation des nœuds

Les nœuds sont les structures de base de nos graphes. Cependant, le contenu réel d’un nœud dépend fortement du problème à résoudre : il peut s’agir de gares, de cases sur une grille, de serveurs, de villes...

Nous créons donc une classe abstraite Node, qui contiendra les informations nécessaires pour les algorithmes. Cette classe doit être héritée pour la résolution pratique d’un problème.

Les nœuds ont besoin de trois informations :

Nous utilisons des propriétés. Pour les deux premières, elles possèdent des valeurs par défaut.

public abstract class Node 
{ 
    private Node precursor = null; 
    internal Node Precursor 
    { 
        get 
        { 
            return precursor; 
        } 
        set 
        { 
            precursor = value; 
        } 
    } 
 
    private double distanceFromBeginning = double.PositiveInfinity; 
    internal double DistanceFromBeginning 
    { 
        get 
        { 
            return distanceFromBeginning; 
        } 
        set 
        { 
            distanceFromBeginning = value; 
        } 
    } 
 
    internal double EstimatedDistanceToExit { get; set; }
 

b. Classe représentant les arcs

Une fois les nœuds définis, nous pouvons définir les arcs, grâce à la classe Arc. Ceux-ci contiennent trois propriétés :