Bon, regarde pas trop en détails, il y a des trucs pas très jolis (je fais un melange de C et C++dans tous les coins). Pour l'interface graphique, j'ai utilisé gtk sans réel argument.
Pour dijsktra, c'est du "fait maison". En fait avec Disjktra, tu visites une et une seule fois chaque noeud. Le problème c'est qu'avec ca, il te sort qu'un chemin qui minimise "quelquechose", qur lequel on a un ordre total (par exemple, minimiser le temps d'arrivé, le temps de parcours, le nombre de correspondances). Maintenant, si tu mets un ordre partiel, et que tu t'assures qu'il n'y aura jamais trop d'elements minimums, tu peux faire un peu pres la meme chose.
Après, il est possible d'améliorer en pratique le rercherche. Avec disjktra, on a grosso modo du linéaire. Mais quand il y a beaucoup de trains et de gares, ca prend quelque secondes. On peut utiliser des "heuristiques" à la A* pour deviner plus rapidement quel chemin va le mieux marcher, et abandoner le plus tot possible les chemins qui partent pas dans la meme direction.
[^] # Re: De quelle aide as-tu besoin ?
Posté par Michael Rao . En réponse au journal horaires SNCF sous linux. Évalué à 5.
Pour dijsktra, c'est du "fait maison". En fait avec Disjktra, tu visites une et une seule fois chaque noeud. Le problème c'est qu'avec ca, il te sort qu'un chemin qui minimise "quelquechose", qur lequel on a un ordre total (par exemple, minimiser le temps d'arrivé, le temps de parcours, le nombre de correspondances). Maintenant, si tu mets un ordre partiel, et que tu t'assures qu'il n'y aura jamais trop d'elements minimums, tu peux faire un peu pres la meme chose.
Après, il est possible d'améliorer en pratique le rercherche. Avec disjktra, on a grosso modo du linéaire. Mais quand il y a beaucoup de trains et de gares, ca prend quelque secondes. On peut utiliser des "heuristiques" à la A* pour deviner plus rapidement quel chemin va le mieux marcher, et abandoner le plus tot possible les chemins qui partent pas dans la meme direction.
(J'ai fait une these en algo de graphes :) )