developvbdebut
Messages postés476Date d'inscriptionsamedi 14 août 2004StatutMembreDernière intervention 2 juin 2012
-
28 mai 2007 à 22:53
The_Guardian
Messages postés317Date d'inscriptionvendredi 25 mai 2007StatutMembreDernière intervention19 octobre 2007
-
31 mai 2007 à 22:20
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.
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);
The_Guardian
Messages postés317Date d'inscriptionvendredi 25 mai 2007StatutMembreDernière intervention19 octobre 20071 28 mai 2007 à 23:52
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
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é.
The_Guardian
Messages postés317Date d'inscriptionvendredi 25 mai 2007StatutMembreDernière intervention19 octobre 20071 29 mai 2007 à 11:41
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.
=
Vous n’avez pas trouvé la réponse que vous recherchez ?
/*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.
The_Guardian
Messages postés317Date d'inscriptionvendredi 25 mai 2007StatutMembreDernière intervention19 octobre 20071 31 mai 2007 à 22:20
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