Plus court chemin d'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.
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
-
Contributeurbonjour, 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); } -
Contributeur@hugotu as généré un graphe orienté. pourquoi penses-tu le contraire?
je vois plusieurs erreurs dans ton code, prends le temps de les corriger. -
@yg_bepour moi il est non orienté car j'ai mis même poids sur les deux arêtes
,G.temps[i][j]=a; G.temps[j][i]=a;
ici a est le même pour les deux arêtes. -
Contributeur@hugoil s'agit donc bien d'un graphe orienté.
je vois plusieurs erreurs dans ton code, prends le temps de les corriger. -
@yg_bedans quels parties tu pense qu'il y a des erreurs?
-
