Chemins extrémaux des graphes pondérés
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étrique1.
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 absorbant2. 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.
- 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égatifs3. - Poids positifs ou nuls. Exemple : l'algorithme de Moore-Dijkstra3.
- Poids tous égaux. Exemple : l'algorithme de Moore-Dijkstra modifié4.
- Un chemin minimal entre la racine (départ) et le sommet d'arrivée5.
- Un chemin minimal entre la racine (départ) et chacun des autres sommets6.
- Un chemin minimal entre chaque couple de sommets7.
English translation
You have asked to visit this site in English. For now, only the interface is translated, but not all the content yet.If you want to help me in translations, your contribution is welcome. All you need to do is register on the site, and send me a message asking me to add you to the group of translators, which will give you the opportunity to translate the pages you want. A link at the bottom of each translated page indicates that you are the translator, and has a link to your profile.
Thank you in advance.
Document created the 28/12/2009, last modified the 26/10/2018
Source of the printed document:https://www.gaudry.be/en/graphes-chemin.html
The infobrol is a personal site whose content is my sole responsibility. The text is available under CreativeCommons license (BY-NC-SA). More info on the terms of use and the author.
- ↑ Orienté symétrique : Nous pouvons remplacer chaque arête d'un arc non orienté par deux arcs aux directions oposées.
- ↑ 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.
- ↑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.
- ↑ 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.
- ↑ Racine -> arrivée : Algorithme heuristique A* si la destination est préalablement déterminée, mais chaque algorithme de type racine -> ∀sommet convient.
- ↑ Racine -> ∀sommet : En général, ce type d'algorithme n'est pas plus compliqué qu'un algorithme racine -> arrivée.
- ↑ ∀sommet -> ∀sommet : Algorithmes qui utilisent une matrice mise à jour au cours d'itérations successives.
References
INFOB321 - Théorie des graphes : JP Leclercq, Cours de Théorie des Graphes et réseaux de Petri
(September 2008)
These references and links indicate documents consulted during the writing of this page, or which may provide additional information, but the authors of these sources can not be held responsible for the content of this page.
The author This site is solely responsible for the way in which the various concepts, and the freedoms that are taken with the reference works, are presented here. Remember that you must cross multiple source information to reduce the risk of errors.
