Inscription / Connexion Nouveau Sujet
Niveau algorithmique
Partager :

algorithme sur graphe complet

Posté par
abricomateux
05-11-16 à 17:18

Bonjour
On considère un graphe complet valué à n sommets.
Existe-t-il un algorithme de complexité au plus O(n^3) qui, pour 2 points du graphes, trouve le chemin qui minimise la longueur de la plus longue arrete traversée, et renvoie cette longueur...
J'ai en fait trouvé un tel algorithme,mais en O(n^4), peut on faire plus rapide?

Posté par
fred1992
re : algorithme sur graphe complet 06-11-16 à 00:39

Salut. Étant donné un graphe donné et deux sommets de ce graphe,  si j'ai bien compris, on cherche à obtenir le chemin le plus court (que les arêtes soient pondérées ou non) entre ces deux sommets, dans ce cas, Djikstra ne convient-il pas ?

Posté par
abricomateux
re : algorithme sur graphe complet 06-11-16 à 11:53

Non, le but ce n'est pas de trouver le plus court chemin entre deux points. Pour imager un peu, on veut aller d'un point A a un point B en faisant des pauses (les sommets), et le but est de trouver le chemin dont la distance maximale entre deux pauses est minimale...
Par exemple, si on prend les points de coordonnées suivantes:
A=(0;0)
B=(4;0)
C=(-1;3)
D=(2;4)
E=(5,3)
L'algorithme va trouver que le meilleur chemin est ACDEB et va retourner la distance de la plus grande arrete de ce chemin, ici \sqrt{10}

Répondre à ce sujet

Seuls les membres peuvent poster sur le forum !

Vous devez être connecté pour poster :

Connexion / Inscription Poster un nouveau sujet
Une question ?
Besoin d'aide ?
(Gratuit)
Un modérateur est susceptible de supprimer toute contribution qui ne serait pas en relation avec le thème de discussion abordé, la ligne éditoriale du site, ou qui serait contraire à la loi.


Vous devez être membre accéder à ce service...

Pas encore inscrit ?

1 compte par personne, multi-compte interdit !

Ou identifiez-vous :


Rester sur la page

Désolé, votre version d'Internet Explorer est plus que périmée ! Merci de le mettre à jour ou de télécharger Firefox ou Google Chrome pour utiliser le site. Votre ordinateur vous remerciera !