Bonjour à tous ! 

Je travaille actuellement sur un projet qui consiste à prendre une carte quelconque (de ville principalement) et d'y calculer le plus court chemin pour aller d'un point important A à un autre B. J'ai déjà codé un algorithme de calcul du plus court chemin (sur le modèle de celui de Dijkstra), mais ce dernier ne fonctionne qu'en prenant en entrée une matrice d'adjacence. Pour expliquer très brièvement, la matrice d'adjacence d'un graphe dont les sommets sont numérotés par des entiers de 0 à n, le coefficient (i, j) i.e à la ième ligne et jième colonne est un -1 si il n'y a pas de chemin du sommet i au sommet j, et sinon contient la valeur du poids de ce dernier (exemple, si le chemin à un poids de 10, la valeur du coefficient est 10).

Mon problème est donc de pouvoir à partir d'une carte, obtenir une matrice d'adjacence. Du moins, il faut que je trouve un moyen de calculer à l'aide d'un programme python la distance qui sépare deux points donnés, pour pouvoir ensuite en déduire la matrice associée. Ma première idée est la suivante : je passe un filtre noir et blanc qui transforme la carte en sa copie conforme, mais en noir en blanc. Je peux ensuite "suivre" les routes pixel par pixel avec le module Python PIL. Je n'ai pas encore terminé le dit programme, mais j'aimerai déjà avoir votre avis sur la question : Est-ce que cela peut aboutir, ou bien est-ce que je devrais plutôt chercher une autre solution, et le cas échéant, toute idée ou recommandation est la bienvenue. 

En espérant avoir été le plus clair possible.

Merci d'avance pour vos réponses, et désolé pour la longueur. 

Oulà, pour faire ça tu vas devoir avoir recours à l'intelligence artificielle. En effet, je pense que la solution que tu proposes va trouver des millions de petites routes partout.

Bonjour,

Le plus simple est de voir directement avec une API google si tu peux avoir la position GPS de chaque ville et considère une ligne droite entre les 2 (distance euclidienne ou géodésique). Ce ne sera pas extrêmement précis, mais utiliser une carte en image et faire les chemins avec un algo de remplissage, tu vas y passer un temps monstre ne serais-ce que pour debugger. Honnêtement, je ne sais pas comment sont faite les cartes comme waze / google map pour le suivi de route mais si c'est un projet pour apprendre, c'est déjà bien. 

Concernant l'algo, pour les cartes, le mieux est le A* avec comme heuristique la distance géodésique/euclidienne si tu cherches le plus court chemin. Si tu veux le plus rapide, je ne sais pas trop quelle heuristique prendre mais la distance euclidienne doit être pas trop mal (sachant que tu prendre distance / vitesse du segment comme distance de nodes). Si tu veux la plus économe, je ne sais pas du tout... je pense qu'il faut regarder comment fonctionne les fourmies (c'est ce que Waze fait btw)