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
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
4 réponses
BunoCS
Messages postés
15472
Date d'inscription
lundi 11 juillet 2005
Statut
Modérateur
Dernière intervention
25 mars 2024
103
27 mai 2005 à 09:17
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...
<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...
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
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 !!!
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és
22
Date d'inscription
dimanche 11 janvier 2004
Statut
Membre
Dernière intervention
31 janvier 2006
31 mai 2005 à 20:25
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.
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és
240
Date d'inscription
dimanche 31 octobre 2004
Statut
Membre
Dernière intervention
31 décembre 2006
2
1 juin 2005 à 09:52
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 !!!
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 !!!
