Floyd-Warshall ou n fois Dijkstra?
Forum 'Discussions' - Sujet créé le 2011-10-24
Bonsoir,
Je cherche la façon la plus pertinente pour trouver tous les plus court chemin entre tous les couples de noeud d'un sous-graphe.
Soit G(E,V) un graphe orientée avec des arcs dans l'ensemble E de poids positif et un ensemble de noeuds V de taille n.
Je considére un sous-ensemble U (de taille n') de V.
Je cherche à calculer tous les plus court chemin entre les couples de noeud de U dans le graphe G.
Une première approche serait d'utiliser l'algorithme de Floyd-Warshall.
Je n'arrive pas à voir comment l'adapter à mon problème sans effectuer une triple boucle sur V. Peut-on gagner en complexité avec une modification de l'algorithme et faire certaines boucles uniquement sur U. (Désolé si je m'explique mal.)
Pour le moment je suis donc à une complexité de O(n^3).
La seconde possibilité serait d'utiliser n' fois l'algorithme de Dijkstra. On aurait donc une complexité de O(n'.n^2.log(n)).
J'ai vu que l'on pouvait améliorer cette approche en utilisant les tas de Fibonacci. J'attend de voire si cette solution est la meilleure pour approfondir dans cette voie.
Peut-on améliorer Floyd-Warshall pour ce cas particulier?
Comment exploiter correctement les tas de Fibonacci?
Merci d'avance.
Je cherche la façon la plus pertinente pour trouver tous les plus court chemin entre tous les couples de noeud d'un sous-graphe.
Soit G(E,V) un graphe orientée avec des arcs dans l'ensemble E de poids positif et un ensemble de noeuds V de taille n.
Je considére un sous-ensemble U (de taille n') de V.
Je cherche à calculer tous les plus court chemin entre les couples de noeud de U dans le graphe G.
Une première approche serait d'utiliser l'algorithme de Floyd-Warshall.
Je n'arrive pas à voir comment l'adapter à mon problème sans effectuer une triple boucle sur V. Peut-on gagner en complexité avec une modification de l'algorithme et faire certaines boucles uniquement sur U. (Désolé si je m'explique mal.)
Pour le moment je suis donc à une complexité de O(n^3).
La seconde possibilité serait d'utiliser n' fois l'algorithme de Dijkstra. On aurait donc une complexité de O(n'.n^2.log(n)).
J'ai vu que l'on pouvait améliorer cette approche en utilisant les tas de Fibonacci. J'attend de voire si cette solution est la meilleure pour approfondir dans cette voie.
Peut-on améliorer Floyd-Warshall pour ce cas particulier?
Comment exploiter correctement les tas de Fibonacci?
Merci d'avance.