Bonjour,
voilà j'ouvre un topic de plus sur Dijkstra et le cacul du chemin le plus court dans un graphe.
 
Donc j'arrive bien à calculer le chemin le plus court en terme de distance mais pas en terme de temps pour une raison très simple : sur chaque point de mon graphe j'ai des horaires de départ (et donc d'arrivé, horaire de départ + durée du trajet).
 
C'est donc le cas, par exemple, d'un réseau ferroviaire. Ce n'est pas forcément le trajet le plus court en distance qui sera le plus court en temps.
 
Donc actuellement je cherche un moyen de caculer le trajet le plus court tout en conservant mon implémentation de Dijkstra. J'ai une petite idée de solution justement : ça consiste à ajouter à chaque arrête de mon graphe le temps d'attente en gare. A priori ça me semble assez logique et ça devrait fonctionner.
 
Le problème c'est que je peux eventuellement me retrouver avec des graphes assez important et que l'ajout du temps d'attente sur chaque arrête prend pas mal de temps puisqu'a chaque fois il faut, en fonction de l'heure d'arrivée à une gare, trouver l'heure de départ la plus proche et ainsi calculer le temps d'attente. A faire sur tout le graphe, avec un graphe de taille assez importante c'est pas terrible.
 
Je me demandais donc s'il n'y avait pas une solution un peut plus rapide/optimisée pour calculer le chemin le plus court en temps en tennant compte des horaires de départ disponibles? J'imagine quand même que je ne suis pas le premier à être confronté à ce genre de problème, cela dit je n'ai rien trouvé sur le net, ni sur le forum. Sauf peut être le fait de travailler avec plusieurs niveaux, je ne sais pas encore comment utiliser ça mais à mon avis ça devrait m'aider un peu.
 
Voilà, si quelqu'un a une idée, un lien, etc.
D'avance, merci.

Bon et bien...
 

et pourquoi tu remplaces pas la valuation en distance de tes arètes par une valuation en temps? Genre, entre tel point et tel point, faut tant de minutes (ou d'heures)...

En fait le problème ne se situe pas là, puisque valuer les arètes en fonction du temps de parcours ou de la distance ça revient au même finalement. Puisque la distance est proportionnelle au temps de parcourt.
 
En revanche, c'est les temps d'attente éventuels en gare qui peuvent changer la durée totale de parcourt d'un chemin et ainsi le rendre plus long à parcourir qu'un autre qui serait plus long en distance.

 
ben non, les temps ne sont pas forcément proportionnels aux distances. Sur un plan concret, tu fais plus de distance sur l'autoroute que sur une départementale pour un même temps...  
 
Pour en revenir à ton pb, là, comme ça, j'ai pas de meilleure idée que de rajouter des arètes et des points supplémentaires sur ton graphe qui représenteraient les temps d'attente (mais distance nulle).
 
Côté algo, regardes peut-être du côté de la programmation dynamique ou des algos génétiques (je verrais bien des fourmis se balader sur ton graphe pour trouver le + court trajet en temps).

Je ne dis absolument pas le contraire, mais dans mon cas c'est plus ou moins vrai. Et puis que ce soit la distance ou la durée de parcourt c'est connu à l'avance.

Ouai tiens je vais chercher de ce côté c'est pas bête.

ca m'etonnerais quand meme pas qu'il existe un algo optimal pour ce probleme, regarde p'tet du coté des methodes utilisées pour l'ordonnancement, vu que ca ressemble fortement a un probleme d'ordo tout ça.

Et pourquoi ne pas tout simplement considerer chaque heure de depart comme un noeud different?
edit pour l'explication: en fait ca revient a considerer que les noeuds ton graphe ne sont plus des villes, mais des trajets (i.e une provenance, une destination, une heure de depart et une heure d'arrivee)

Ptit détérage... ^^
 
A mon avis aussi il n'existe pas d'algo optimal pour ce genre de probleme...
Je suppose qu'en plus le temps d'attente a chaque gare doit etre dynamique.
 
En effet l'idée de créer des "doubles noeuds" a l'air interessante, par contre si le temps d'attente est bien dynamique il va falloir le récupérer a chaque noeud.
 
 
Sinon ca doit sans doute etre fesable d'approcher une solution optimale le plus possible (heuristique?) par une solution qui nous conviendrait globalement. A mon avis c'est le genre de compromis que font certains sites que nous connaissons qui doivent a la fois etre performant niveau vitesse de calcul, et avoir un résultat relativement correct...
 
Dans ce cas ce que tu peux faire par exemple est de modifier l'algorithme pour optenir le plus cours chemin en terme de distance, puis récupérer également les chemins qui auraient une distance légerement supérieure a cette distance minimale (a toi de définir le seuil selon tes besoins rapidité/robustesse), et faire le calcul en temps sur chacun de ces chemins pour définir quel va etre au final ton plus cours chemin.
Quand tu fais baisser le seuil, tu vas te rapprocher de l'algorithme classique qui ne prend en compte que les distances, et quand tu fais monter le seuil, tu vas te rapprocher de la solution de Ace qui prend plus de temps de calcul.
 
Ici j'ai considéré qu'en gros les trains passent relativement régulierement  et que ca roule globalement a la meme vitesse partout sur le reseau... Et le seuil est la pour corriger les petites "erreurs"
Apres il est clair que si tu as des trains avec une attente de 5h alors que d'autres ont 10min d'attente, ma solution est loin d'etre la meuilleur, mais au moins ca te donnera peut etre des idées...

et tu gères les correspondances au fait ?
 
parceque c'est pas trop utile de trouver un chemin plus court plus rapide si tu ne gères pas les correspondances.
 
très souvent, prendre un train rapide sur 90% du trajet, puis faire les 10% restants en tortillard, c'est bien plus rapide que faire 100% de tortillard, seule solution directe.
 
et c'est pas tout, faut gérer le coût aussi. par exemple, si tu vas de A à B avec B juste avant C et une ligne directe vers B, y'a pas beaucoup de monde qui voudra payer deux fois la section "B-C" juste pour le plaisir de gagner 5 minutes.
 
(courage, à dans 6 mois )

Ouai bon là tu prends en compte toute sorte de critères... Dans mon cas il s'agissait bien d'un réseaux ferroviaire mais complètement virtuel. La question du coût du trajet, ou encore de sa complexité n'était pas déterminant dans le choix, seul le temps de parcourt.
 
Finalement je m'en suis sorti en testant tous les trajets possibles... C'est loin d'être super en temps/ressources utilisé, mais les différentes solutions que j'avais à tester n'était pas assez nombreuses pour que ce soit vraiment gênant.

 
 
 
Hello, aurais-tu une valeur pour le temps/ressource utilisés?

Non pas de valeurs...
Si je retrouve ça je ferais quelques test.
 
Bon après c'est variable, moi je faisais tourner ça avec 5/6 gares et une dizaines de trains dans la journée au total. Donc rien de bien méchant.
 
Mais vu qu'aucune limite n'a été fixée, avec un peu de courage on pouvait bien envoyer 60'000'000 de trains sur 20'000'000 de gares. Mais là... je penses que code tient pas.

hein quoi t'as pas géré les greves, les attentats, les suicides, les déraillages, les coupures d'alimentation??? mais il est nul ton programme

Non, il est idéaliste rien d'autre.

Dans le cas où l'ordre de grandeur de tes données en entrées (nb gares et trains) viendrait à grandir, je pense que tu pourrais utiliser un algo génétique. A chaque itération, tu génères aléatoirement une population d'individus ou chaque individu représente un trajet. La fonction de valuation est le temps du trajet. A chaque itération, tu gardes le meilleur individu et tu fais une sélection d'individus+croisement+éventuelle mutation pour générer la population de l'itération suivante. A toi de voir sur quels critères tu fais ta sélection d'individus et comment tu fais le croisement et la mutation...et le nb d'itérations est à définir aussi J'avais fait un truc de ce genre pour optimiser la perte d'espace sur des CD lorsque je donnais en entrée un nb de cds à utiliser et une liste de fichiers à graver, mais il n'était pas obligé de prendre tous les fichiers. En gros, c'était pour répondre à la question : "parmi cette liste de fichiers, lesquels je dois prendre pour minimiser la perte d'espace si j'utilise n CD vierges?" (la capacité totale des CD pouvant être < à la taille totale des fichiers).
http://chris-jav.servhome.org/projects_optcd.php

Oui tu m'avais déjà proposé d'utiliser un algo génétique pour résoudre le problème de façon plus optimale (voir ton post plus haut). Cela-dit, et même si je vois bien "l'analogie" possible, j'ai quand du mal implémenter ce genre de choses.
 
Vais m'y remettre, ça me fera de l'exercice. Merci pour le lien.