Le 24/10/2011 par holdo :

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.