IdentifiantMot de passe
Loading...
Mot de passe oublié ?Je m'inscris ! (gratuit)
Navigation

Inscrivez-vous gratuitement
pour pouvoir participer, suivre les réponses en temps réel, voter pour les messages, poser vos propres questions et recevoir la newsletter

C Discussion :

chemin le plus court sur un graphe


Sujet :

C

Vue hybride

Message précédent Message précédent   Message suivant Message suivant
  1. #1
    Membre régulier
    Homme Profil pro
    Étudiant
    Inscrit en
    Avril 2019
    Messages
    8
    Détails du profil
    Informations personnelles :
    Sexe : Homme
    Âge : 26
    Localisation : France, Yvelines (Île de France)

    Informations professionnelles :
    Activité : Étudiant

    Informations forums :
    Inscription : Avril 2019
    Messages : 8
    Par défaut 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.

  2. #2
    Membre très actif
    Avatar de sambia39
    Homme Profil pro
    No Comment
    Inscrit en
    Mai 2010
    Messages
    548
    Détails du profil
    Informations personnelles :
    Sexe : Homme
    Localisation : France, Loiret (Centre)

    Informations professionnelles :
    Activité : No Comment
    Secteur : High Tech - Matériel informatique

    Informations forums :
    Inscription : Mai 2010
    Messages : 548
    Par défaut
    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,

  3. #3
    Membre régulier
    Homme Profil pro
    Étudiant
    Inscrit en
    Avril 2019
    Messages
    8
    Détails du profil
    Informations personnelles :
    Sexe : Homme
    Âge : 26
    Localisation : France, Yvelines (Île de France)

    Informations professionnelles :
    Activité : Étudiant

    Informations forums :
    Inscription : Avril 2019
    Messages : 8
    Par défaut
    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 : Sélectionner tout - Visualiser dans une fenêtre à part
    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);
    }

  4. #4
    Membre prolifique
    Avatar de Sve@r
    Homme Profil pro
    Ingénieur développement logiciels
    Inscrit en
    Février 2006
    Messages
    12 832
    Détails du profil
    Informations personnelles :
    Sexe : Homme
    Localisation : France, Oise (Picardie)

    Informations professionnelles :
    Activité : Ingénieur développement logiciels
    Secteur : Aéronautique - Marine - Espace - Armement

    Informations forums :
    Inscription : Février 2006
    Messages : 12 832
    Billets dans le blog
    1
    Par défaut
    Bonjour
    Citation Envoyé par hugo1999 Voir le message
    bonjour, je connais le langage C je sais plus ou moins programmer dans ce langage.
    Code : Sélectionner tout - Visualiser dans une fenêtre à part
    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 ???
    Mon Tutoriel sur la programmation «Python»
    Mon Tutoriel sur la programmation «Shell»
    Sinon il y en a pleins d'autres. N'oubliez pas non plus les différentes faq disponibles sur ce site
    Et on poste ses codes entre balises [code] et [/code]

  5. #5
    Membre régulier
    Homme Profil pro
    Étudiant
    Inscrit en
    Avril 2019
    Messages
    8
    Détails du profil
    Informations personnelles :
    Sexe : Homme
    Âge : 26
    Localisation : France, Yvelines (Île de France)

    Informations professionnelles :
    Activité : Étudiant

    Informations forums :
    Inscription : Avril 2019
    Messages : 8
    Par défaut
    Code : Sélectionner tout - Visualiser dans une fenêtre à part
    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 ?

  6. #6
    Membre très actif
    Avatar de sambia39
    Homme Profil pro
    No Comment
    Inscrit en
    Mai 2010
    Messages
    548
    Détails du profil
    Informations personnelles :
    Sexe : Homme
    Localisation : France, Loiret (Centre)

    Informations professionnelles :
    Activité : No Comment
    Secteur : High Tech - Matériel informatique

    Informations forums :
    Inscription : Mai 2010
    Messages : 548
    Par défaut
    Citation Envoyé par hugo1999 Voir le message
    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


    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

Discussions similaires

  1. Réponses: 6
    Dernier message: 17/12/2013, 00h42
  2. Réponses: 3
    Dernier message: 13/11/2012, 09h47
  3. Chemin le plus court dans un graphe en parallèle
    Par arkerone dans le forum Algorithmes et structures de données
    Réponses: 2
    Dernier message: 11/11/2012, 15h43
  4. Requete recursive - Graphe - Chemin le plus court
    Par nicottin dans le forum SQL
    Réponses: 7
    Dernier message: 08/11/2007, 00h33
  5. algorithme de Ford (recherche chemin le plus court)
    Par abstraite dans le forum Algorithmes et structures de données
    Réponses: 2
    Dernier message: 19/05/2005, 10h39

Partager

Partager
  • Envoyer la discussion sur Viadeo
  • Envoyer la discussion sur Twitter
  • Envoyer la discussion sur Google
  • Envoyer la discussion sur Facebook
  • Envoyer la discussion sur Digg
  • Envoyer la discussion sur Delicious
  • Envoyer la discussion sur MySpace
  • Envoyer la discussion sur Yahoo