Plus court chemin d'un graphe
hugo
-
hugo -
hugo -
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.
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.
Configuration: Windows / Internet Explorer 11.0
1 réponse
-
yg_be Messages postés 23437 Date d'inscription Statut Contributeur Dernière intervention Ambassadeur 1 588
bonjour, as-tu commencé ton programme? peux-tu le partager?
dans quel contexte fais-tu cela?
l'algorithme de Floyd–Warshall est peut-être plus simple à programmer.-
bonjour, pour l'instant j'ai seulement générer un graphe aléatoirement et j'ai mis un poids sur les arêtes. je dois faire cela dans le cadre d'un projet. il me semble que l'algorithme de Floyd fonctionne pour un graphe orienté.
#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); } -
-
-
-
-
