Plus court chement avec le cout

Signaler
Messages postés
476
Date d'inscription
samedi 14 août 2004
Statut
Membre
Dernière intervention
2 juin 2012
-
Messages postés
317
Date d'inscription
vendredi 25 mai 2007
Statut
Membre
Dernière intervention
19 octobre 2007
-
Bonsoir tout le monde

J'ai un probleme avec l'algo du plus cours chemin, je ne vois pas comment mis prendre.


De plus, je dois affichier la distance entre la ville de départ est la ville d'arrivé.


Je suis un peu perdue au niveau de l'algo à mettre en place.


j'ai regardé une source de floyd, mai je n'ais rien compris.

Dans le graph.h

#ifndef GRAPH_H
#define GRAPH_H




 



#include <stdlib.h>
#include <stdio.h>
#include <limits.h>



#define INFINI INT_MAX



#define a 18
#define b 2




 





const char* tableau [a][b]={
     "1","St-quentin",
     "2","Cambrai",
     "3","Capelle",
     "4","Laon",
     "5","Noyon",
     "6","Peronne",
     "7","Roye",
     "8","Avesne",
     "9","Charleville-Meziere",
     "10","Vervins",
     "11","Reins",
     "12","Soisson",
     "13","Amiens",
     "14","Compiegne",
     "15","Bapaume",
     "16","Arras",
     "17","Douai",
     "18","Valenciennes"};





struct table{





char de;
char ar;
};





struct liste{



int parcouru;
int villeprecedent;
char pasencoreVue;
char dejaVue;




 



};




 





#endif



Dans le graph.c

#include <stdlib.h>
#include <stdio.h>
#include "graph.h"




 





struct table tab;
struct liste lis;



void result(){
    
    
    
    
    
}



void recherche(char tabl[a][b],int distance,char depa,char arriv){
int i;
int n_parcouru, n_precedent;
    for(i=0;i<a;i++){
            
         n_parcouru = INFINI;   
         n_precedent=0;          
        }



        lis.parcouru=0;
                        
                
                
         



}







Cordialement

6 réponses

Messages postés
476
Date d'inscription
samedi 14 août 2004
Statut
Membre
Dernière intervention
2 juin 2012
1
Re

pardon il n'ya pas tout le code du graph.c

Le voici

#include <stdlib.h>
#include <stdio.h>
#include "graph.h"




 





struct table tab;
struct liste lis;



void result(){
    
    
    
    
    
}



void recherche(char tabl[a][b],int distance,char depa,char arriv){
int i;
int n_parcouru, n_precedent;
    for(i=0;i<a;i++){
            
         n_parcouru = INFINI;   
         n_precedent=0;          
        }



        lis.parcouru=0;
       




 



}




 



void saisie()
{



int i,j;



int cout=0;   
   
    puts("Bienvenue a la SNCF\n");
   
    for(i=0;i<a;i++){
         
          for(j=0;j<b;j++){
               
            printf(" %s",tableau[i][j]);   
               
               
               
                }
          puts("\n");
         
         
          }
    puts("\n");
    puts("Entrer l'indice de la ville du debut de parcours");
    scanf("%c",&tab.de);
    puts("Entrer l'indice de la ville de fin de parcours");
    scanf("%c\n",&tab.ar);  
    
    
     /**/
    
     recherche(tableau,cout,tab.de,tab.ar);
    
    
     /*fin de programme*/
    system("PAUSE");
    
}


A+
Messages postés
317
Date d'inscription
vendredi 25 mai 2007
Statut
Membre
Dernière intervention
19 octobre 2007

Salut,

Bon alors ta fonction recherche est pas trop mal, le debut en tout cas effectivement, tu fais la bonne initialisation, mais il te manque l'etape d'apres
de l'algorithme de Dijkstra.
pour i de '0' a 'a' faire
   indice <--- l'indice de la ville non parcourue ayant la plus petite distance parcourue.
pour j de '0' a 'a' faire
si il y a une route entre la ville 'k' et la ville 'indice' alors si la ville 'j' n'est pas dans la liste.
ta fonction recherche devrait etre comme ca


visite = tableau de n booleens
precedent = tableau de n entiers
distance = tableau de n entiers


initialement
- tous les elements de visite sont a FAUX
- toutes les distances sont a 10000
distance[depart] = 0
pour i de 1 a n faire
  ville <-- indice de la ville ayant la plus petite distance telle que visite[ville]==FAUX
  pour j de 1 a n faire
    si il y a une route entre ville et j alors
      si visite[j]==FAUX alors
        si distance[ville]+cout(ville, j)<distance[j] alors
          distance[j] = distance[ville]+cout(ville, j)
          precedent[j] = ville
        finsi
      finsi
    finsi
  finpour
  visite[ville] = VRAI
finpour

=
Messages postés
476
Date d'inscription
samedi 14 août 2004
Statut
Membre
Dernière intervention
2 juin 2012
1
bonjour tout le monde

J'ai un doute concernant le tableau des villes

Voici comment mon était donnée le villes dans le fichier text avec le TP.

st-quentin 6
cambrai 39
capelle 50
laon 52
noyon 40
peronne 29
roye 48



capelle 5
avesnes 16
cambrai 54
charleville-mezieres 68
st-quentin 50
vervins 17



laon 4
reims 45
soissons 32
st-quentin 52
vervins 32



noyon 3
compiegne 24
roye 20
st-quentin 40



roye 5
amiens 41
compiegne 39
noyon 20
peronne 31
st-quentin 48



peronne 4
amiens 52
bapaume 20
roye 31
st-quentin 29



cambrai 7
arras 37
avesnes 59
bapaume 30
capelle 54
douai 39
st-quentin 39
valenciennes 26


dois je mettre en forme le tableau exactement ainsi, en ajoutant les une colonne pour les kilomêtre et au ajoutant plusieurs  fois les villes, l'algo en s'aura t'il modifié.

Merci.

A+
Messages postés
317
Date d'inscription
vendredi 25 mai 2007
Statut
Membre
Dernière intervention
19 octobre 2007

RE

l'algo que je t'ai montre est un algo de recherche pour initialiser tes donnees, il te faut un autre algo que je vais te donner maintenant:
deja il te faut un tableau de noms de villes
string nomDesVilles[10];
nomDesVilles[0] = "cambrai" par exemple, etc
ensuite il te faut un tableau a deux dimensions pour les distances
int distances[10][10];tu initialises toutes les cases a INFINI, puis apres tu lis tes distances dans le fichier on voit que st-quentin / cambrai 39, donc tu mets nomDesVilles[1][0] 39 et nomDesVilles[0][1] = 39 (ici j'ai suppose st-quentin est la ville numero 1)
 Voila tu fais ca pour toutes les villes de ton fichier texte et apres ca sera bon.

=
Messages postés
476
Date d'inscription
samedi 14 août 2004
Statut
Membre
Dernière intervention
2 juin 2012
1
Bonsoir tout le monde

graph.h

#ifndef GRAPH_H
#define GRAPH_H



/**/



#include <stdlib.h>
#include <stdio.h>
#include <limits.h>



#define INFINI INT_MAX



#define a 18
#define b 18
#define c 18
#define d 2



/**/





#define STQUENTIN 0
#define CAMBRAI 1
#define CAPELLE 2
#define LAON 3
#define AVESNES 4
#define CHARLEVILLEMEZIERES 5
#define REIMS 6
#define SOISSONS 7
#define VERVINS 8
#define NOYON 9
#define ROYE 10
#define AMIENS 11
#define COMPIEGNE 12
#define PERONNE 13
#define ARRAS 14
#define BAPAUME 15
#define DOUAI 16
#define VALENCIENNE 17





/**/





const char* tableau [c][d]={
     "1","St-quentin",
     "2","Cambrai",
     "3","Capelle",
     "4","Laon",
     "5","Noyon",
     "6","Peronne",
     "7","Roye",
     "8","Avesne",
     "9","Charleville-Meziere",
     "10","Vervins",
     "11","Reins",
     "12","Soisson",
     "13","Amiens",
     "14","Compiegne",
     "15","Bapaume",
     "16","Arras",
     "17","Douai",
     "18","Valenciennes"};
    
    
/**/    





/*Ci-dessou la structure*/



struct table{





int km;
char destination;
char source;
char de;
char ar;
};





/*Ci-dessou*/



struct liste{





int villeprecedent;
char pasencoreVue;




 





};




 





#endif


graph.c

#include <stdlib.h>
#include <stdio.h>
#include "graph.h"




 





struct table tab;
struct liste lis;



int distance[18][18]={INFINI};



void result(){
    
    
    
    
    
}



int dist(){
   
int i,j;
/*ici on initialise les distances*/



distance[STQUENTIN][CAMBRAI]=39;
distance[STQUENTIN][CAPELLE]=50;
distance[STQUENTIN][LAON]=52;
distance[STQUENTIN][NOYON]=40;
distance[STQUENTIN][PERONNE]=29;
distance[STQUENTIN][ROYE]=48;



distance[CAPELLE][AVESNES]=16;
distance[CAPELLE][CAMBRAI]=54;
distance[CAPELLE][CHARLEVILLEMEZIERES]=68;
distance[CAPELLE][STQUENTIN]=50;
distance[CAPELLE][VERVINS]=17;





distance[LAON][REIMS]=45;
distance[LAON][SOISSONS]=32;
distance[LAON][STQUENTIN]=52;
distance[LAON][VERVINS]=32;



distance[NOYON][COMPIEGNE]=24;
distance[NOYON][ROYE]=20;
distance[NOYON][STQUENTIN]=40;



distance[ROYE][AMIENS]=41;
distance[ROYE][COMPIEGNE]=39;
distance[ROYE][NOYON]=20;
distance[ROYE][PERONNE]=31;
distance[ROYE][STQUENTIN]=48;



distance[PERONNE][AMIENS]=52;
distance[PERONNE][BAPAUME]=20;
distance[PERONNE][ROYE]=31;
distance[PERONNE][STQUENTIN]=29;



distance[CAMBRAI][ARRAS]=37;
distance[CAMBRAI][AVESNES]=59;
distance[CAMBRAI][BAPAUME]=30;
distance[CAMBRAI][CAPELLE]=54;
distance[CAMBRAI][DOUAI]=39;
distance[CAMBRAI][STQUENTIN]=39;
distance[CAMBRAI][VALENCIENNE]=26;   
   
  puts("les chemins\n"); 
   
  for(i=0;i<a;i++){
         
          for(j=0;j<b;j++){
               
                if(distance[i][j]==INFINI){
                                          
                                          
                printf(" -- ");   
               
                }
                else { printf("%d ", distance[i][j]); }
                }
          puts("\n");    
}



          for(i=0;i<a;i++){
                       
              for(j=0;j<b;j++){
                   
                 distance[i][j] = INFINI;     
         
         
                 }     
          }



}



/*Voici l'algorithme de Dijkstra, pour le plus cours chemin*/



int recherche(char tabl[][b],int cout[][18],char dep,char arriv){
    
/*là on déclare des des variables pour*/    
    
int i,j;





     for(i=1;i<a;i++){
 
          for(j=1;j<b;j++){
               
            cout[i][j]=INFINI;   
           
                }
           cout[i][j]=0;
         }
                       
     while(cout!=0){
        
        
        
        
         tab.source=dep;
        
         for(i=1;i<lis.pasencoreVue;i++){
              
              
          tab.destination= arriv;   
              
              
              
               }
        
          
           }
    




 




 



return recherche(tabl,cout,tab.source,tab.destination);
}



/*ici c'est la fonction de départ, c'est là que l'on choisira sont parcourt
audémarage un tableau s'affichera avec les villes.
*/



void saisie()
{



int i,j;
  
   
    puts("Bienvenue a la SNCF\n");
   
    for(i=0;i<c;i++){
         
          for(j=0;j<d;j++){
               
         
                printf(" %s", tableau[i][j]);
               
               
                }
          puts("\n");
         
         
          }
    puts("\n");
   
    /*Vous devrez saisir votre ville de départ et la ville d'arrivée*/
    puts("Entrer l'indice de la ville du debut de parcours");
    scanf("%c",&tab.de);
    puts("Entrer l'indice de la ville de fin de parcours");
    scanf("%c\n",&tab.ar);  
    
    
     /*ici on appelle la fonction recherche qui aura l'algorithme de Dijkstra
     la fonction utilisera cette algorithme pour determiner le chemin le plus court
     avec un cout minimum*/
    
     recherche(tableau,distance,tab.de,tab.ar);
    
    
     /*fin de programme*/
    system("PAUSE");
    
}

******


La il, je suis perdue pour l'algo de la fonction recherche, je veux utiliser la fonction recherche avec la fonction dist qui contien les distances.

Donc, au final je souhait lors que l'on choisi une ville de départ et une ville d'arrivé , je veux que l'algo calcu le plus cours chemin et le cout.

Exemple

On part de Douai pour aller à Capelle, on devra passer par cambrai, le cout sera de 93 km, je souhaite que ca s'affiche.

Est ce que c'est possible.

Merci

A +
Messages postés
317
Date d'inscription
vendredi 25 mai 2007
Statut
Membre
Dernière intervention
19 octobre 2007

RE

y'a pas mal de trucs a corriger sur ton programme..

Bon donc dans la fonction recherche, tu commences avec l'initialisation du tableau cout, ok
sauf que tu as mis cout[i][j] = 0 et ca doit etre cout[i][i] = 0
ensuite ton while est faux
L'algo est le suivant:
tantque la ville que je recherche est pas visitee faire

Mince c'est quoi ton code là. C'est ni fait, ni a faire en fait!

Bon on reprend depuis début.
Pour l'algo de dijkstra tu as besoin des variables suivantes
un tableau a une dimension cout
un tableau a une dimension visite
donc ton initialisation dans la fonction recherche est fausse
Ensuite l'algo est le suivant:
cout[source] = 0
tantque visite[destination]=faux faire
ville <--- la ville non visitee ayant le plus petit cout
pour toute autre ville v faire
si cout[v]>cout[ville]+distance[v][ville] alors
cout[v] = cout[ville]+distance[v][ville]
  finsi
  finpour
visite[ville] = vrai
 fintantque

Tu risques d'avoir des problemes dans ton test car tu as utilise INT_MAX et c'est pas forcement le mieux, enfin du moment que tu fais les tests qui vont bien ca posera pas de problemes

=


 


Ps: c'est toi tintin ?