Recherche du plus court chemin

Signaler
Messages postés
1
Date d'inscription
mardi 18 mai 2004
Statut
Membre
Dernière intervention
10 janvier 2005
-
Messages postés
4297
Date d'inscription
samedi 19 janvier 2002
Statut
Modérateur
Dernière intervention
9 janvier 2013
-
Je suis à la recherche d'une implémentation d'un algorithme de calcul du plus court chemin sous Delphi. La méthode importe peu (Dijkstra / Moore / Floyd).

Merci davance

Doume

5 réponses

Messages postés
470
Date d'inscription
vendredi 14 novembre 2003
Statut
Membre
Dernière intervention
23 octobre 2007
1
salut,

genre tu lui donne trois chemins et il te di lekel est le + court ?
en donnant une vitesse pour chaque chemin ?

Filipe
Messages postés
240
Date d'inscription
dimanche 31 octobre 2004
Statut
Membre
Dernière intervention
31 décembre 2006
2
Tiens je vais te donner le pseudo-code de la procedure de marquage en
largeur et de l'algorithme de djisktra, il te restera plus qu'a les
traduier en pascal (je vais pas tout faire à ta place :p)



on cherche un pcc de s vers les autres sommets



PM en largeur

Soit V[x] la longueur d'un chemin minimal de s vers x

La valeur des arc doivent être une constante pour cet algo



On initialise le tableau V a l'infini

V[s] = 0

viderFile (Q)

EnQueue(Q,s)

Répéter

Dequeue(Q,i)

Pour tout j successeur de i avec V[j] = infini faire

V[j] = V[i] + k

Enqueue(Q,j)

Fin de pour

Jusqu'a PileVide(Q) = true



Dijskra

N : le nombre de sommet

Wij : le cout de l'arc ij

A : l'ensemble des sommets indexés

X : l'ensemble des sommets du graph



On initialise V a l'infini

V[s] = 0

A = {s}

Pour tout i successeur de s faire

V[i] = Wsi {Wsi le cout du chemin de s à i}

Fin de Pour

Pour iter = 1 à (N-1) faire

chercher i appartenant à X-A tel que V[i] soit minimal

Si V[i] < infini alors

A = A + { i }

Pour tout successeur j de i non dans A faire

Si V[i] + W ij < V[j] alors

V[j] = V[i] + Wij

Fin de Si

Fin de Pour

Fin de Si

Fin de Pour


Voila voila, il te reste plus qu'a le traduire en pascal, mais je t'assure qu'il marche !!!

Alors bonne prog et a++
Messages postés
47
Date d'inscription
mardi 18 mai 2004
Statut
Membre
Dernière intervention
24 juillet 2006

Je suis d'accord avec sim51. L'algorithme de Djikstra est vraiment très
simple. Et tu ira surement beaucoup plus vite à l'implémenter en
fonction de tes données existente que d'adapter une implémentation
existante à tes données.



C'est encore plus vrai pour les algorithmes à heuristique comme A* (Djikstra peut être très long sur des grands graphes).
Messages postés
240
Date d'inscription
dimanche 31 octobre 2004
Statut
Membre
Dernière intervention
31 décembre 2006
2
Oui il faut que tu prenne l'algo de dijskra même si sa complexité est
de l'ordre de o(n^2), c'est le plus simple et le plus adaptable à
n'importe quel situation.

Cependant, si tu as un graph avec plus de 200 sommets, ils existe
un autre algo de dijskra avec l'utilisation d'un tas, ce qui rend sa
complexité à o(m log n) mais qui est un peu plus complexe à coder.

Sinon j'ai bien une procédure de dijskra chez moi, mais pour le
transcrire à ton problème tu vas t'amiser, c'est pourquoi je t'ai donné
le pseudo code, alors amuse toi bien !!!



N'oublie de cliker sur reponse accepté :p
Messages postés
4297
Date d'inscription
samedi 19 janvier 2002
Statut
Modérateur
Dernière intervention
9 janvier 2013
31
Je ne suis pas un spécialiste de la question et je viens juste de tomber sur un ouvrage qui t'intéressera au plus haut point, notamment le chapitre 6 disponible en ligne à la librairie Eyrolles en pdf (41 pages pour se régaler).
Cerise sur le gâteau : toutes les implémentations sont en pascal

Pensez à cliquer sur Réponse acceptée lorsque la réponse vous convient.
http://www.croix-rouge.fr/index/partner_campagne.html