Chemins extrémaux des graphes pondérés

Sommaire du document

Les pages suivantes décrivent certains algorithmes utilisés pour trouver des chemins extrémaux dans un graphe (pathfinding).

Selon les données que nous possédons sur le graphe de départ, nous devrons sélectionner quel algorithme exécuter, en fonction de ses possibilités et de ses performances.

Typologie des problèmes

En fonction des données du graphe de départ, nous pouvons donc formuler un certain nombre d'hypothèses parmi celles évoquées ci-dessous.

H1 : Graphe orienté

L'hypothèse H1 présume que le graphe est orienté. Il s'agit presque d'un axiome, car nous pouvons considérer tout graphe non orienté comme un graphe orienté symétrique^[1].

H2 : Chemin minimum

Ce que nous recherchons le plus souvent comme chemin dans un graphe, c'est le chemin de poids (de coût) minimum. Parfois, il est nécessaire de chercher le chemin de poids maximum (par exemple dans le cas d'un gain).

Dans nos exemples d'algorithmes de recherches de chemins extrémaux, nous prendrons la convension de rechercher le chemin minimum.

H3 : Graphes simplement connexes

L'hypothèse H3 présume que le graphe est simplement connexe.

H4 : Pas de boucles

L'hypothèse H4 présume que le graphe ne contient pas de boucles.

H5 : Racine

L'hypothèse H5 présume que le graphe possède une racine, qui est le point de départ de notre chemin.

Si notre graphe ne possède pas de racine (ou s'il possède plus d'une racine), nous pouvons ajouter un sommet de départ, qui deviendra notre racine. Nous devons alors relier ce sommet à tout sommet candidat racine (sommet racine, ou sommet isolé) par un arc de poids zéro.

H6 : Pas de circuit absorbant

L'hypothèse H6 présume que le graphe ne possède pas de circuit absorbant^[2]. Un circuit absorbant n'est pas borné, et il tend à l'infini.

Classification des algorithmes

En fonction des différentes hypothèses que nous pouvons formuler à propos d'un graphe, nous pouvons orienter notre choix d'algorithme à utiliser.

• Circuits 
  • Absence de circuit. Exemple : l'algorithme de Moore-Dijkstra retourne un chemin qui n'est pas optimum si nous n'avons pas de circuit.
  • Présence de circuit. Exemple : on ne peut pas utiliser l'algorithme de Bellman-Kalaba.
• Nature du poids des arcs
  • Poids quelconques. Le marquage ne peut plus être définitif. Exemples :
    l'algorithme de Ford-Bellman utilise la méthode d'ajustement progressif.
    l'algorithme de Bellman-Kalaba fonctionne quand-même si le graphe ne comporte pas de circuit.
    l'algorithme de Moore-Dijkstra ne fonctionnera pas en présence d'arcs de poids négatifs^[3].
  • Poids positifs ou nuls. Exemple : l'algorithme de Moore-Dijkstra^[3].
  • Poids tous égaux. Exemple : l'algorithme de Moore-Dijkstra modifié^[4].
• Nombre de chemins minimaux recherchés
  • Un chemin minimal entre la racine (départ) et le sommet d'arrivée^[5].
  • Un chemin minimal entre la racine (départ) et chacun des autres sommets^[6].
  • Un chemin minimal entre chaque couple de sommets^[7].

Notes

1. ↑ Orienté symétrique : Nous pouvons remplacer chaque arête d'un arc non orienté par deux arcs aux directions oposées.
   
   
2. ↑ Circuit absorbant : Un circuit absorbant, dans le cas d'un chemin minimal, est un circuit pour lequel chaque passage diminue le poids du chemin. C'est le contraire pour un chemin maximal.
   
   
3. ↑^a,b Moore-Dijkstra & poids négatifs : L'algorithme de Moore-Dijkstra ne permet pas la présence de pondération négative dans notre exemple car nous sommes à la recherche de chemin extrême minimum. Dans le cas de la recherche d'un chemin extrême maximum avec l'algorithme de Moore-Dijkstra le graphe ne peut contenir aucun arc de pondération positive, et nous devons légèrement modifier le pseudo code.
   
   
4. ↑ Moore-Dijkstra modifié : Dans la version modifiée de l'algorithme de Moore-Dijkstra, nous utilisons un ensemble de sommets marqués simultanément lors d'une seule itération.
   
   
5. ↑ Racine -> arrivée : Algorithme heuristique A^* si la destination est préalablement déterminée, mais chaque algorithme de type racine -> ∀sommet convient.
   
   
6. ↑ Racine -> ∀sommet : En général, ce type d'algorithme n'est pas plus compliqué qu'un algorithme racine -> arrivée.
   
   
7. ↑ ∀sommet -> ∀sommet : Algorithmes qui utilisent une matrice mise à jour au cours d'itérations successives.
   
   

Références

1. INFOB321 - Théorie des graphes : JP Leclercq, Cours de Théorie des Graphes et réseaux de Petri (Septembre 2008)

Ces références et liens indiquent des documents consultés lors de la rédaction de cette page, ou qui peuvent apporter un complément d'information, mais les auteurs de ces sources ne peuvent être tenus responsables du contenu de cette page.
L'auteur de ce site est seul responsable de la manière dont sont présentés ici les différents concepts, et des libertés qui sont prises avec les ouvrages de référence. N'oubliez pas que vous devez croiser les informations de sources multiples afin de diminuer les risques d'erreurs.

Structure du document