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
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
A voir également:
- Mvn : le terme «mvn» n'est pas reconnu comme nom d'applet de commande, fonction, fichier de script ou programme exécutable. vérifiez l'orthographe du nom, ou si un chemin d'accès existe, vérifiez que le chemin d'accès est correct et réessayez.
- Verification nom de domaine - Forum PHP
- L'accès au chemin d'accès est refusé - Forum ASP / ASP.NET
- Generateur nom de domaine - Forum Visual Basic
- Generateur de nom de jeu ✓ - Forum C# / .NET
- Qu'est-ce qu'un document en accès concurrent ? - Forum C
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
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
genre tu lui donne trois chemins et il te di lekel est le + court ?
en donnant une vitesse pour chaque chemin ?
Filipe
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
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++
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++
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
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).
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).
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
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
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
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
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
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