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

Signaler
Messages postés
22
Date d'inscription
dimanche 11 janvier 2004
Statut
Membre
Dernière intervention
31 janvier 2006
-
Messages postés
240
Date d'inscription
dimanche 31 octobre 2004
Statut
Membre
Dernière intervention
31 décembre 2006
-
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

Messages postés
14982
Date d'inscription
lundi 11 juillet 2005
Statut
Modérateur
Dernière intervention
2 mars 2021
94
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...
Messages postés
240
Date d'inscription
dimanche 31 octobre 2004
Statut
Membre
Dernière intervention
31 décembre 2006
1
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 !!!
Messages postés
22
Date d'inscription
dimanche 11 janvier 2004
Statut
Membre
Dernière intervention
31 janvier 2006

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.
Messages postés
240
Date d'inscription
dimanche 31 octobre 2004
Statut
Membre
Dernière intervention
31 décembre 2006
1
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 !!!