AIDE SVP. comment determiner les chemins dans un graphe en language C
arthur007
Messages postés22Date d'inscriptiondimanche 11 janvier 2004StatutMembreDernière intervention31 janvier 2006
-
26 mai 2005 à 22:37
cs_sim51
Messages postés240Date d'inscriptiondimanche 31 octobre 2004StatutMembreDernière intervention31 décembre 2006
-
1 juin 2005 à 09:52
Bonjour à tous,
Aidez moi, svp. j'en vraiment besoin
je cherche un exemple de code en language C, ou une explication, pour calculer (determiner) les chemins possibles d'un somment à l'autre d'un graphe. aussi si le graphe et connexe..;ect ou le chemin le plus court...
Merci d'avance
cs_sim51
Messages postés240Date d'inscriptiondimanche 31 octobre 2004StatutMembreDernière intervention31 décembre 20062 27 mai 2005 à 10:16
Salut,
Alors en effet bruno t'a donné tout les algo possible sur les graph
(quoique il manque le couplge lol ). Mais je vais t'aider un peu plus.
Je vais te donner le pseudo code de la procédure en largeur pour la
recherche des chemin et de dijkstra pour les plus courts chemin.
PM en largeur
Soit V[x] un tableau ou si V[i]=0 i est accessible de s et si V[j]=infini alors j n'est pas accessible
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] = 0
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
V[i] : la valeur du chemin de s à i
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
Voilà maintenant il ne te reste plus qu'a le traduire en C en prenant en compte la structure de ton graph.
Bon courage
N'oubliez pas de cliquer sur réponse acceptée si la réponse vous convient !!!
arthur007
Messages postés22Date d'inscriptiondimanche 11 janvier 2004StatutMembreDernière intervention31 janvier 2006 31 mai 2005 à 20:25
bonjour,
Merci pour votre réponse, je vais essayer de faire avec. Surtout j'ai vu que la marorité des exemple sont en C++ et moi je veux des exemple en C. peut etre pas grande difference, mais co meme.
cs_sim51
Messages postés240Date d'inscriptiondimanche 31 octobre 2004StatutMembreDernière intervention31 décembre 20062 1 juin 2005 à 09:52
arthur007,
Cela ne sert à rien de prendre le code de qq1 d'autre, en effet cela ne va pas forcement correspondre au codage de ton graph, certaine personne utilise des matrice d'adjacence, d'autres des matrices n*n etc.
Moi je t'ai donné le pseudo code des procédure, c'est toi de l'adapter pour qu'il corresponde à ton type de donné.
Puis c'est tellement gratifiant de faire une procédure qui marche.
Alors à ton clavier lol
N'oubliez pas de cliquer sur réponse acceptée si la réponse vous convient !!!