AIDE SVP. comment determiner les chemins dans un graphe en language C

arthur007 Messages postés 22 Date d'inscription dimanche 11 janvier 2004 Statut Membre Dernière intervention 31 janvier 2006 - 26 mai 2005 à 22:37
cs_sim51 Messages postés 240 Date d'inscription dimanche 31 octobre 2004 Statut Membre Dernière intervention 31 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

4 réponses

BunoCS Messages postés 15475 Date d'inscription lundi 11 juillet 2005 Statut Modérateur Dernière intervention 23 avril 2024 103
27 mai 2005 à 09:17
Algorithmes de plus court chemin



<li>Algorithme de Dijkstra
</li><li>Algorithme de
Dantzig
</li><li>Algorithme de Ford-Bellman
</li>






Algorithme d'arbres couvrant minimaux



<li>Algorithme de Kruskal
</li><li>Algorithme de
Prim </li>






Algorithme pour les flots maximums



<li>Algorithme
de Ford-Fulkerson
</li><li>Algorithme de
Roy </li>






Algorithmes de parcours de graphe



<li>Algorithme de parcours en
largeur (ou BFS: Breadth first search)
</li><li>Algorithme de parcours en
profondeur (ou DFS: Depth First Search) </li>







Pour plus de détails, Google....

Buno
----------------------------------------
L'urgent est fait, l'impossible reste à faire. Pour les miracles, prévoir un délai...
1
cs_sim51 Messages postés 240 Date d'inscription dimanche 31 octobre 2004 Statut Membre Dernière intervention 31 décembre 2006 2
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 !!!
0
arthur007 Messages postés 22 Date d'inscription dimanche 11 janvier 2004 Statut Membre Dernière intervention 31 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.
0
cs_sim51 Messages postés 240 Date d'inscription dimanche 31 octobre 2004 Statut Membre Dernière intervention 31 décembre 2006 2
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 !!!
0
Rejoignez-nous