chemin le plus court sur un graphe

Bonjour,
je cherche a implémenter un programme qui me permettrais d'avoir le plus court chemin entre deux sommets d'un graphe. Je n'ai pas vraiment d'idée de comment je pourrais faire cela, je connais l'algorithme de Dijkstra mais je ne sais pas comment l'implémenter en c et l'adapter a ma structure de graphe( matrice adjacente avec un poids entre deux sommets). Si quelqu'un a une petite idée ou connais un autre algorithme de ce type je suis preneur. Merci d'avance.

Bonjour,

On pourrait vous aider, mais encore faut-il clarifier les choses. Quand vous dites, je ne sais pas comment l’implémenter en langage de programmation « C » l’algorithme de Dijkstra, c’est parce que vous ne savez pas par où commencer en partant du fait que vous connaissez le langage de programmation C ou vous ne savez pas par où commencer parce que vous ne connaissez pas/débutez en langage de programmation C.

Et pour un début d'implémentation, vous pouvez représenter votre graphe à l’aide de tableau à deux dimensions comme ceci size_t graphe[5][5];, c’est également valable pour votre matrice d’adjacence (ou si vous êtes à l’aise avec les structures de données comme les listes chaînées, vous pouvez faire une liste d’adjacence).

En ce qui concerne d’autres algorithmes, il y a par exemple l'algorithme de Ford et celui Bellman connue le plus souvent sous le nom de Bellman-Ford ou Ford Bellman. Il y a également celui de Floyd-Warshall ceci dit avant de s’attaquer à d’autres algorithmes commencés d’abord par implémenter celui de Dijkstra.

À bientôt,

bonjour, je connais le langage C je sais plus ou moins programmer dans ce langage. Pour l'instant j'ai générer un graphe aléatoire avec un poids sur les arêtes. Le problème est que je ne sais pas comment m'y prendre pour trouver le chemin minimum.

Code:

---

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56

#include <stdio.h> #include <stdlib.h> #include <time.h>     typedef struct {   int matrice_adjacence[50][50]; int temps[50][50]; } graphe;   graphe init_graphe(){   graphe G ; int i; int j; for(i = 0 ; i <50 ; i ++){ for(j = 0 ; j <49 ; j++){   G.matrice_adjacence[i][j] = 0; }   } return G; }   graphe alea_graphe(){ graphe G; for(int i=0; i<50 ; i++){   int j =rand()%50; G.matrice_adjacence[i][j]=1; G.matrice_adjacence[j][i]=1; int a=rand()%30; G.temps[i][j]=a; G.temps[j][i]=a;   } return G; }   void affiche_graphe(graphe G){ int i,j; printf("Graphe avec %d sommets \n",50); for(i = 0; i<50; i++){ printf("Voisins de %d: ",i); for(j = 0; j < 50; j++){ if(G.matrice_adjacence[i][j]) printf("%d ",j); } printf("\n"); } }   int main(){ graphe g; g=init_graphe(); g=alea_graphe(); affiche_graphe(g); }

---

Bonjour

Citation:

---

Envoyé par hugo1999

bonjour, je connais le langage C je sais plus ou moins programmer dans ce langage.

Code:

---

1 2	g=init_graphe(); g=alea_graphe();

---

---

Plutôt moins que plus. Il n'y a rien qui te choque là ? Je ne sais pas moi. Par exemple ça te semble logique d'écrire i=5; i=6 ??? Et si oui, alors dis-moi à quoi sert la première instruction ???

Code:

---

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56

#include <stdio.h> #include <stdlib.h> #include <time.h>     typedef struct {   int matrice_adjacence[50][50]; int temps[50][50]; } graphe;   graphe init_graphe(){   graphe G ; int i; int j; for(i = 0 ; i <50 ; i ++){ for(j = 0 ; j <49 ; j++){   G.matrice_adjacence[i][j] = 0; }   } return G; }   graphe alea_graphe(){ graphe G=init_graphe(); for(int i=0; i<50 ; i++){   int j =rand()%50; G.matrice_adjacence[i][j]=1; G.matrice_adjacence[j][i]=1; int a=rand()%30; G.temps[i][j]=a; G.temps[j][i]=a;   } return G; }   void affiche_graphe(graphe G){ int i,j; printf("Graphe avec %d sommets \n",50); for(i = 0; i<50; i++){ printf("Voisins de %d: ",i); for(j = 0; j < 50; j++){ if(G.matrice_adjacence[i][j]) printf("%d ",j); } printf("\n"); } }   int main(){ graphe g;   g=alea_graphe(); affiche_graphe(g); }

---

J'ai corrigé, est-ce bon ?

Citation:

---

Envoyé par hugo1999

J'ai corrigé, est-ce bon ?

---

Attention à cette phrase ; c’est être volontaire pour peloton d’exécution dont les projectiles qui vont vous atteindre sont du calibre 5,56 standard OTAN du genre « Nous ne sommes pas là pour déboguer le programme à votre place. » qui est utilisé par les forums informatiques d’entraide. En cas de guerre totale, c’est du calibre 50 à utiliser avec ZPU-4 :ptdr:


Blague à part, je vous invite à revoir le code et faire simple : à commencer par corrigez les erreurs qui sont dans votre code pour avoir une bonne base par où commencer l'implémentation d'un algorithme en langage C. Cas contraire ici

j'ai essayer de modifier un peu le code, je n'ai pas d'erreurs de compilation.

Code:

---

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61

#include <stdio.h> #include <stdlib.h> #include <time.h>   typedef struct { //graphe représenté par une matrice d'adjacence int nombre_sommet; int ** matrice_adjacence; int ** temps; } graphe;     void affiche_graphe(graphe G){ int i,j; printf("Graphe avec %d sommets \n",G.nombre_sommet); for(i = 0; i<G.nombre_sommet; i++){ printf("Voisins de %d: ",i); for(j = 0; j < G.nombre_sommet; j++){ if(G.matrice_adjacence[i][j]) printf("%d ",j); } printf("\n"); } }   graphe init_graphe(int n){//créé un graphe dont tous les sommets sont isolés   graphe G ; int i; G.nombre_sommet=n; G.matrice_adjacence=malloc(sizeof(int*)); for(i=0; i<n; i++) G.matrice_adjacence[i]=calloc(n,sizeof(int));   return G; }     graphe alea_graphe(int n, float p){ graphe G=init_graphe(n); for(int i=0; i<n-2; i++){ for(int j=0; j<n-1; j++){ if(rand()%100 <p*100) {G.matrice_adjacence[i][j]=1; G.matrice_adjacence[j][i]=1; int t=rand()%30; G.temps[i][j]=t; G.temps[j][i]=t;   }   } } return G; }     int main(){ srand(time(NULL)); graphe L; L=alea_graphe(10, 0.2); affiche(L);   }

---