|
L'algorithme du chemin le plus rapide dépend fortement des caractéristiques spécifiques de votre graphique :
1. Nature du graphique :
* Pondéré ou non pondéré : Les arêtes de votre graphique sont-elles associées à un coût ou à une distance (pondérées), ou toutes les arêtes sont-elles considérées comme ayant le même coût (non pondéré) ?
* Dirigé ou non : Les bordures sont-elles directionnelles (rues à sens unique) ou bidirectionnelles (rues à double sens) ?
* Cyclique ou acyclique : Le graphique contient-il des cycles (chemins pouvant ramener au même nœud) ?
* Densité : Le graphique est-il clairsemé (relativement peu d’arêtes) ou dense (beaucoup d’arêtes) ?
* Poids non négatifs : Tous les poids des bords sont-ils non négatifs ? Ceci est *crucial* pour que de nombreux algorithmes fonctionnent correctement. Si vous avez des poids négatifs, une manipulation particulière est nécessaire.
* Euclidien vs non-euclidien : Pouvez-vous utiliser des propriétés géométriques pour déduire les distances entre des points ?
2. Objectif de l'algorithme :
* Chemin le plus court à source unique : Trouver le chemin le plus court depuis un nœud de départ spécifique vers tous les autres nœuds du graphique.
* Chemin le plus court à destination unique : Recherche du chemin le plus court entre tous les nœuds et un nœud de destination spécifique (conceptuellement identique à celui d'une source unique si vous inversez la direction des bords).
* Chemin le plus court de toutes les paires : Trouver le chemin le plus court entre *chaque* paire de nœuds dans le graphique.
* Heuristiques autorisées ? Si vous êtes d'accord avec une approximation et que vous n'avez pas la garantie du chemin le plus court *absolu*, vous pouvez souvent obtenir des résultats beaucoup plus rapides avec la recherche heuristique.
Voici une présentation des algorithmes courants et de leurs cas d'utilisation typiques :
Pour les graphiques non pondérés :
* Recherche en largeur d'abord (BFS) : Il s'agit de l'algorithme *le plus rapide* et le plus simple pour les graphiques non pondérés. Il garantit la recherche du chemin le plus court (en termes de *nombre* d'arêtes) depuis un nœud source vers tous les autres nœuds accessibles.
* Complexité temporelle : O(V + E) où V est le nombre de sommets et E est le nombre d'arêtes.
Pour les graphiques pondérés avec des pondérations non négatives :
* Algorithme de Dijkstra : L'un des algorithmes les plus largement utilisés pour trouver le chemin le plus court entre une source unique et tous les autres nœuds dans un graphique pondéré avec des poids de bord *non négatifs*.
* Complexité temporelle :
* O(V^2) (avec une implémentation simple de tableau ou de liste pour la file d'attente prioritaire)
* O(E + V log V) (en utilisant un tas binaire ou une file d'attente prioritaire)
* O(E + V log* V) (en utilisant des tas de Fibonacci - moins courant en pratique en raison des frais généraux)
* A* Recherche : Une extension de l'algorithme de Dijkstra qui utilise une fonction *heuristique* pour guider la recherche. C'est souvent beaucoup plus rapide que celui de Dijkstra lorsque vous disposez de bonnes informations heuristiques sur la distance restante jusqu'à la destination.
* Complexité temporelle : Cela dépend de l'heuristique. Dans le meilleur des cas (heuristique parfaite), cela peut être très rapide. Dans le pire des cas (mauvaise heuristique), cela peut être aussi lent que celui de Dijkstra.
* A* nécessite une heuristique admissible (ne surestime jamais le coût pour atteindre l'objectif) et cohérente (monotone).
Pour les graphiques pondérés avec des poids négatifs (et sans cycles négatifs) :
* Algorithme Bellman-Ford : Peut gérer des graphiques avec des poids de bord négatifs, tant qu'il n'y a pas de cycles négatifs (cycles où la somme des poids de bord est négative). Si un cycle négatif existe, il peut le détecter.
* Complexité temporelle : O(V*E)
Pour les chemins les plus courts de toutes les paires :
* Algorithme Floyd-Warshall : Trouve le chemin le plus court entre *chaque* paire de sommets dans un graphe orienté ou non. Il peut également gérer des poids de bord négatifs (mais pas des cycles négatifs).
* Complexité temporelle : O(V^3)
* Algorithme de Johnson : Peut également trouver les chemins les plus courts de toutes les paires et gérer les poids de bord négatifs. Il est généralement plus rapide que Floyd-Warshall sur les graphiques * clairsemés *. Il fonctionne en repondérant les arêtes pour éliminer les poids négatifs (à l'aide de Bellman-Ford), puis en exécutant l'algorithme de Dijkstra à partir de chaque sommet.
* Complexité temporelle : O (V ^ 2 log V + VE)
Tableau récapitulatif
| Algorithme | Type de graphique | Poids des bords | Complexité temporelle | Remarques |
| ------------------ | --------------------------------------------- | ------------ | -------------------------- | --------------------------------------------------------------- |
| BFS | Non pondéré | Aucun | O(V+E) | Le plus rapide pour les graphiques non pondérés. |
| de Dijkstra | Pondéré, non négatif | Non négatif | O(E + Vlog V) | Commun, fonctionne bien avec la file d'attente prioritaire. |
| A* | Pondéré, non négatif | Non négatif | Dépendant de l'heuristique | Peut être beaucoup plus rapide que celui de Dijkstra si une bonne heuristique existe. |
| Bellman-Ford | Pondéré, peut avoir des bords négatifs | N'importe quel | O(V*E) | Peut détecter les cycles négatifs. |
| Floyd-Warshall | Pondéré, peut avoir des bords négatifs (pas de cycles) | N'importe quel | O(V^3) | Chemins les plus courts de toutes les paires, parfaits pour les graphiques denses. |
| Johnson | Pondéré, peut avoir des bords négatifs (pas de cycles) | N'importe quel | O (V ^ 2 log V + VE) | Chemins les plus courts de toutes les paires, meilleurs que Floyd-Warshall pour les graphiques clairsemés |
Considérations pratiques et optimisations :
* Structures de données : Le choix de la structure de données pour la file d'attente prioritaire dans l'algorithme de Dijkstra (par exemple, tas binaire, tas de Fibonacci) peut avoir un impact significatif sur les performances, en particulier pour les grands graphes.
* Heuristiques pour A* : Choisir une bonne heuristique pour A* est crucial. Une heuristique bien choisie peut considérablement accélérer la recherche. Les heuristiques courantes incluent la distance euclidienne (pour les graphiques intégrés dans un plan) et la distance de Manhattan.
* Représentation graphique : La façon dont vous représentez votre graphique (par exemple, liste de contiguïté, matrice de contiguïté) peut également affecter les performances. Les listes de contiguïté sont généralement préférées pour les graphes clairsemés, tandis que les matrices de contiguïté peuvent être plus efficaces pour les graphes denses.
* Prétraitement : Pour les graphiques interrogés à plusieurs reprises, vous pouvez précalculer certaines informations (par exemple, les points de repère, les arbres de chemin le plus court) pour accélérer les requêtes ultérieures.
* Réseaux routiers du monde réel : Pour les réseaux routiers, des algorithmes spécialisés tels que les hiérarchies de contraction (CH) et la planification d'itinéraire personnalisable (CRP) offrent des temps de requête *beaucoup* plus rapides que les algorithmes génériques comme celui de Dijkstra, mais ils nécessitent un prétraitement important. Ceux-ci sont souvent utilisés dans les systèmes de navigation GPS.
* Bibliothèques : Utilisez des bibliothèques optimisées (par exemple, NetworkX en Python, JGraphT en Java) autant que possible. Ces bibliothèques fournissent souvent des implémentations hautement optimisées d’algorithmes de chemin le plus court.
En résumé, pour déterminer l'algorithme "le plus rapide" adapté à votre situation :
1. Caractérisez votre graphique : Est-il pondéré, non pondéré, dirigé, clairsemé, dense, etc. ?
2. Avez-vous besoin des chemins les plus courts provenant d'une source unique ou de toutes les paires ?
3. Des poids de bord négatifs sont-ils présents ? Si tel est le cas, vous êtes limité à Bellman-Ford (source unique) ou Johnson's/Floyd-Warshall (toutes les paires).
4. Si les poids sont non négatifs, considérez celui de Dijkstra ou A*. Si A*, pouvez-vous concevoir une bonne heuristique ?
5. Pour les graphiques non pondérés, BFS est presque toujours le meilleur choix.
6. Profil et benchmark : Expérimentez avec différents algorithmes et structures de données pour voir lequel fonctionne le mieux sur votre ensemble de données et votre matériel spécifiques.
Choisissez l'algorithme le plus simple qui répond à vos besoins. N'utilisez pas Floyd-Warshall si vous n'avez besoin que des chemins les plus courts à source unique.
|
