Recherche du plus court chemin

Planete Mars Messages postés 1 Date d'inscription mardi 18 mai 2004 Statut Membre Dernière intervention 10 janvier 2005 - 10 janv. 2005 à 17:13
cs_Delphiprog Messages postés 4297 Date d'inscription samedi 19 janvier 2002 Statut Membre Dernière intervention 9 janvier 2013 - 13 janv. 2005 à 20:53
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

Filipe35 Messages postés 470 Date d'inscription vendredi 14 novembre 2003 Statut Membre Dernière intervention 23 octobre 2007 1
10 janv. 2005 à 20:59
salut,

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

Filipe
0
cs_sim51 Messages postés 240 Date d'inscription dimanche 31 octobre 2004 Statut Membre Dernière intervention 31 décembre 2006 2
10 janv. 2005 à 23:57
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++
0
sovitec Messages postés 47 Date d'inscription mardi 18 mai 2004 Statut Membre Dernière intervention 24 juillet 2006
11 janv. 2005 à 09:08
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).
0
cs_sim51 Messages postés 240 Date d'inscription dimanche 31 octobre 2004 Statut Membre Dernière intervention 31 décembre 2006 2
12 janv. 2005 à 12:22
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
0

Vous n’avez pas trouvé la réponse que vous recherchez ?

Posez votre question
cs_Delphiprog Messages postés 4297 Date d'inscription samedi 19 janvier 2002 Statut Membre Dernière intervention 9 janvier 2013 32
13 janv. 2005 à 20:53
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
0