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
A voir également:
- Plus court chemin d'un graphe
- 3 bip long 2 bip court hp - Forum BIOS
- Discord aucun chemin de connexion - Forum Discord
- Aucun chemin de connexion discord - Forum Discord
- Court circuit dans l'alimentation de lnb - Forum TNT / Satellite / Réception
- Lien plus court - Guide
1 réponse
yg_be
Messages postés
23437
Date d'inscription
Statut
Contributeur
Dernière intervention
Ambassadeur
1 586
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.
dans quel contexte fais-tu cela?
l'algorithme de Floyd–Warshall est peut-être plus simple à programmer.
#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); }je vois plusieurs erreurs dans ton code, prends le temps de les corriger.
, ici a est le même pour les deux arêtes.
je vois plusieurs erreurs dans ton code, prends le temps de les corriger.