Itinéraire par étapes

Amis Bonjour !

Premier post ici. J'ai découvert excel, le VBA et un peu de SQL sur le tas dans un job il y a près de 10 ans ou je les manipulais beaucoup au quotidien (gestion de base de donnée - stocks en entreprise).

Je me rends compte que je rouille alors j'ai décidé de me lancer de petits défis sur excel. En voici un sur lequel je bloque depuis plusieurs jours. En fait le problème est que je n'arrive même pas à conceptualiser la solution (pour mémoire : je suis un peu un homme des cavernes, pour moi la solution c'est d'abord de taper fort, puis de recommencer).

Considérons un ensemble de lieux, reliés entre eux par des routes. Certains lieux ont 9 routes, d'autres en ont une seule. Sur 51 lieux j'ai 222 routes. Ce que je cherche à faire c'est une sorte de "recherche d'itinéraire". En gros je veux aller du point A au point D, sachant qu'il n'y a pas d'itinéraire direct de A à D. Il faut trouver les correspondances. Je cherche à trouver une formule qui me dise : l'itinéraire est A->C->E->J->D . Sachant que le nombre d'étapes pour aller de A à D peut être variable. Dans l'absolu, voyagessncf fait ça tous les jours alors c'est pas si difficile, ouais ? .... ouais.... Sauf que je ne parviens à rien et que je ne trouve pas de solution avec les fonctions recherche de forums (itinéraire renvoie des topics google maps, adresse et correspondance vous visualisez les topics qu'il me propose).

Ci-joint le fichier. Les plus nerdy d'entre vous reconnaîtront qu'il s'agit des planètes de Freelancer (un vieux jeu qui reste strictement imbattable en termes de gameplay et d'univers ouvert). Il y a donc 51 planètes reliées par des Gates ou des Holes (oui, j'ai même pensé à pouvoir choisir un itinéraire uniquement via les gates ou uniquement via les holes, selon que vous avez envie de trainer dans les bas-fonds loin des autorités ou non - mais pour l'instant considérons qu'on les prend tous). Au total 222 connexions. Je voudrais avoir une sorte de GPS pour pouvoir trouver le meilleur itinéraire d'une planète à l'autre (l'idée étant à terme de calculer quelle est la route commerciale la plus rentable en temps/profit - en gros acheter des marchandises sur telle planète et rejoindre le plus directement possible la planète où je vends ces marchandises au meilleur profit).

En désespoir de cause j'ai fait un truc très moche. J'ai tout simplement créé une grille de 6561 lignes (en gros pour chaque lieu je compte 9 routes possibles, et j'explore chacune des 9 routes possibles de ces 9 lieux). Et je m'arrête à 4 niveaux successifs. Donc 9^4=6561 connexions potentielles testées.

C'est une purge à calculer à chaque fois, c'est laid et inefficace au possible (comme je lui demande d'éviter de m'afficher une planète déjà testée aux étapes précédentes la quasi totalité des lignes est vide). Bref je n'en suis pas fier mais je cale. En plus, 4 étapes c'est insuffisant pour énormément d'itinéraires. Et ajouter ne serait-ce qu'une étape nous ferait passer à 59049 lignes. Proprement inenvisageable.

Je ne suis pas non plus certain qu'une attaque en force brute (itération/valeur cible) soit possible. En tout cas je n'y parviens pas.

Voilà, c'est strictement inutile, c'est même de la perte de temps (j'ai de la compta en retard...) mais bon sang quelle frustration !

Merci d'avance aux plus astucieux d'entre vous ! (et aux autres qui compatissent)

Amicalement,

Ewok

Hello les amis

Je me permets un petit UP. Il faut dire que ça défile vite ici les topics !

Merci à vous

Cordialement

Ewok