Discussion :

[Yyukk]

Bonjour,
Je vais commencer par exposer le probleme auquel je fais face.
Je realise un projet qui a pour but de modeliser un plus court chemin (en utilisant Ocaml et/ou C). Ce plus court chemin est base sur les lignes de metro Parisien.
L'algorithme de Floyd fut choisi pour calculer ce plus court chemin et fonctionne correctement.
Je suis actuellement bloque sur la partie d'implementation et creation du graphe.
Ne sachant pas comment proceder, j'ai fait un petit code en utilisant la ligne de metro marseillaise non exhaustive mais en entrant le nom de toutes les stations

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
(* Types graphes *)
 
type sommet = Sommet of string 
and 'a fleche = sommet * 'a
and 'a graphe = (sommet * ('a fleche) list) list;;
 
let metro_marseille = [ (Sommet "Bougainville",[ (Sommet "National",3)]);
			(Sommet "National", [ (Sommet "Bougainville",3);(Sommet "Desiree_Clary",3)]);
			(Sommet "Desiree_Clary",[(Sommet "National",3);(Sommet "Joliette",3)]);
			(Sommet "Joliette",[ (Sommet "Desiree_Clary",3);(Sommet "Jules_Guesde",3)]);
			(Sommet "Jules_Guesde",[(Sommet "Joliette",3);(Sommet "Gare_St_Charles",5)]);
			(Sommet "Gare_St_Charles",[(Sommet "Jules_Guesde",5);(Sommet "Colbert",5);(Sommet "Noailles",3)]);
			(Sommet "Noailles",[(Sommet "Gare_St_Charles",3);(Sommet "Notre_Dame",4)]);
			(Sommet "Notre_Dame",[(Sommet "Noailles",4);(Sommet "Castellane",3)]);
			(Sommet "Castellane",[(Sommet "Notre_Dame",3);(Sommet "Prefecture",6)]);
			(Sommet "Colbert",[(Sommet "Gare_St_Charles",5);(Sommet "Vieux_Port",3)]);
			(Sommet "Vieux_Port",[(Sommet "Colbert",3);(Sommet "Prefecture",3)]);
			(Sommet "Prefecture",[(Sommet "Vieux_Port",3);(Sommet "Castellane",6)]) ]

Mon programme indique dans une fenetre executable le trajet le plus court pour atteindre a partir d'un point A le point D, mais malheureusement sans afficher le point B et C s'ils existent (que j'aimerai bien indiquer).
Il est evident que faire ainsi pour le metro parisien risque d'etre fastidieux et peu efficace, je voulais donc savoir comment je pouvais proceder et s'il etait possible de generaliser ce code (car je ne vois pas du tout comment faire).

[prgasp77]

Salut, google a trouvé ceci : http://pauillac.inria.fr/~cheno/taupe/poly.pdf
Le chapitre 7 te facilitera (c'est une litote) la tâche.