Je vois qu´Altonfrère a mis en pratique ce qu´il avait proposé sur le topic de JYY pendant que je préparais mon propre training. Celui-ci est destiné aux programmeurs C/C++.

Il s´agit de lire un fichier décrivant un graphe, puis de trouver, à la demande de l´utilisateur, le plus court chemin entre deux points quelconques de ce graphe.
Un graphe peut être décrit comme un ensemble de noeuds ( dans notre cas, des villes), reliés par des arêtes ( ici, des lignes aériennes) dotées d´un poids ( ce poids représentera ici le temps de trajet entre deux villes). Les arêtes sont représentées sous la forme d´un doublon ( But, Temps).
On définit le temps de trajet entre deux villes non reliées directement par la somme des temps de trajets entre les différentes escales.
Le fichier http://mathrim.cauthon.free.fr/Graphes/graphe.jpg est un exemple de graphe. La distance entre les noeuds 2 et 5 est ici de 8.

Il existe un algorithme nommé algorithme de Dijkstra, utilisé pour résoudre les problèmes de plus court chemin.
Le principe en est le suivant:

Initialisation
On cherche à déterminer le plus court chemin entre le noeud A et le noeud B.
On associe à chaque point du graphe un bouléen Examiné, de valeur initial faux, un entier Précédent, de valeur initiale infinie, et un second entier, Distance, de valeur initiale infinie.
Examiné servira à savoir si le noeud a déjà été examiné par l´algorithme, Précédent contient le noeud précédent dans le plus court chemin vers A, et Distance contient la distance minimale entre le noeud et A.

Pour le noeud A:
Précédent = A
Distance = A
Examiné = faux

Enfin, on dispose d´un entier " Pointeur", qui indique le noeud que l´on est en train d´examiner.

Processus
Tant que ( Pointeur ! = B):

Tester l´ensemble des aretes partant de Pointeur:
On appelle But le but de chacune des aretes
Si Examiné(But) n´a pas été testé:
Si Distance(Pointeur) + Temps(Pointeur, But) < Distance(But)
Alors Distance(But) = Distance(Pointeur) + Temps(Pointeur, But)
Et Précédent(But) = Pointeur

Une fois que toutes les aretes ont été testées, on marque que Pointeur a été Examiné.
Pour déterminé le noeud suivant à examiné, on consulte la liste des noeuds qui n´ont pas encore été examiné, et on choisit celui pour lequel la valeur de Distance est la plus faible.

Fin du processus

Finalement, le plus court chemin entre A et B sera Distance(B). Pour trouver exactement ce chemin, il suffit de prendre Précédent(B), puis Précédent(Précédent(B)), etc.. jusqu´à remonter à A.

J´espère que j´ai été assez clair.

Essayez tout d´abord cet algorithme ´à la main´ pour déterminer le plus court chemin entre les noeuds 1 et 5 du graphes, pour vérifier que vous l´avez compris.

Vous trouverez sur http://mathrim.cauthon.free.fr/Graphes/data1.txt un fichier descriptif de graphe.
Son architecture est la suivante:
Première ligne: nombre de noeuds du graphe
Puis:
Nom de la ville
Nombre d´arêtes partant de cette ville
A chaque ligne, Destination de l´arête et Longueur de l´arête, séparés par une tabulation.

Pour programmer ceci:
- écrire une structure de donnée représentant le graphe ( struct ou classe, selon le langage)
- écrire la fonction permettant de remplir le graphe depuis le fichier
- écrire la structure contenant toutes les informations ( examiné, précédent et distance) nécessaire à l´algorithme.
- écrire la fonction implémentant l´algorithme

Je proposerais dans deux semaines un programme effectuant ceci. D´ici là, je suis disponible pour répondre aux questions. Je vous demanderais juste d´écrire le moins de code sur le forum ( afin que chacun chercher par lui-même, ce qui est VRAIMENT nécessaire pour la programmation).

Ah oui, ceux qui le désirent peuvent m´envoyer leur travail par mail ( j´ai l´impression de faire le prof) à mathrim Point cauthon At free Point fr .

ben dis donc, on est loin de mon training rpg maker!
C´est surement du beau travail ( yo no he comprendido)!

Belle astuce pour eviter les robots ramasse mailsaussi.

Si tu rajoute le parametre estimation, c´est pas loin d´un a* effectivement.

/ kUfa

En fait, cet algorithme permet de trouver à coup sûr le plus court chemin entre deux noeuds du graphe.
A* est une généralisation de cette algorithme, qui rajoute le paramètre d´estimation pour diminuer la précision ( il est possible que le chemin retourné ne soit pas le plus court) mais augmenter la vitesse de calcul.

on peut te faire ca dans un autre langage ?
ou c´est interdit ? ( VB ? )

j´ai pensé a une approche très différente pour ca, mais je serais bien incapable de la coder en C.

Je n´ai pas encore tout lu mais c´est très interessant et je vais m´y mettre dans la semaine

«psy

@dnob700: strictement et rigoureusement interdit ! J´écris pour de vrais programmeurs qui utilisent de vrais langages, moi Mossieur !

. ..

Trêve de conneries, bien entendu tu peux le faire en VB. Je ne connais pas du tout par contre ce langage mais je peux répondre aux questions concernant l´algorithmique

Bon courage à tous les deux !

Peux on mettre notre réponse sur une page web perso au lieu de te l´envoyer par mail ?

«psy

Oui, sans problème ; )

tu m´excuseras ( enfin, je l´espère ) , mais j´ai pas bien compris ce qu´un graphe vient foutre la dedans.. c´est juste explicatif ?
sinon j´vais sûrement essayer de le faire, mais j´vais réussir à faire totalement l´inverse

j´crois que j´vais relire ce zouli texte..

L´algorithme à implémenter est un algorithme de recherche de plus court chemin dans un graphe. Le mot " graphe" est ici entendu au sens mathématique du terme ( à savoir, un ensemble de sommets et d´arêtes).

J´ai pas bien tout compris désolé . .. . On peux faire le tout en mode text ou on dois faire une application avec du graphisme ? ( je ne maitrise pas la SDL encore . ..)

«psy

Il faut tout faire en mode texte. La lecture du fichier data1.txt permet de déterminer la structure du graphe, et il " suffit" ensuite de lancer l´algorithme pour trouver le plus court chemin entre deux noeuds.

Ok je voulais juste être sur pour pas avoir l´air con. ^^

«psy

Pas de problème, je suis là pour répondre à toutes les questions sur le training.

Au niveau des librairies, stdio et stdlib suffisent amplement ; )

Je t´avoue que je suis très intéressé, je m´y mets dès que j´ai réinstallé VC++!!!

Juste pour être sur dans le texte c´est écrit :

Londres
4
2 3
3 6
4 9
1 4
Madrid
3
0 4
4 2
5 12
Amsterdam
4
0 3
3 1
6 5
7 2

[...]

La destination c´est le numéro de la ville en commançant par zéro ? donc Amsterdam(ville 2) est relié à Londre(ville 0) par un trait de 3 en distance ?

«psy

Exactement.

A titre de généralisation:
Dans cet exemple, le graphe est " non-orienté", ce qui signifie que les arêtes n´ont pas de sens privilégié. Ainsi, l´arête allant de Londres à Amsterdam est de distance 3, et celle allant de Amsterdam à Londres est de même distance.
Il existe des graphes dans lesquels les arêtes n´indiquent pas toujours les mêmes distances selon le sens.
Par exemple, lorsque le graphe représente les éléments d´une carte comportant une pente, l´arête représentant un chemin en montée sera plus ´longue´ que celle représentant le chemin en descente ( puisqu´il est plus rapide de descendre que de monter).
L´algorithme de Dijkstra fonctionne également dans ce cas.