Algorithme de Dijkstra pour GPS

Bonsoir, pour réaliser un projet, je compte faire un GPS (pas en temps réel) de mon lycée. Un classique du "où je suis"-"où je vais" et le programme affiche le chemin le plus cours. Après quelques recherches j'ai vite compris que j'aurais à utiliser l'algorithme de Dijkstra, j'ai rapidement compris le principe de fonctionnement de cet algorithme, de la lecture du graphe... J'ai donc fait un graphique à la main de mon coté qui se compose de 14 sommets et j'ai pu y calculer le poids des arêtes.
Mais la est le problème, je n'arrive pas programmer tout cela... J'ai introduit mes points avec une matrice adjacente en mettant 1 s'il y a une liaison et 0 s'il y en a pas. Mais c'est tout, j'ai beau avoir cherché je ne sait pas comment continuer, exploiter les points et me lancer dans ce programme... Et mes connaissances assez limité en python (je n'ai que 2h "d'apprentissage" en cours par semaine) me bloque énormément également... C'est pour cela que j'aimerais savoir si ça serais possible de m'aider, de m'expliquer comment procéder... Merci d'avance!

Salut,

C'est pas un problème Python mais d'algorithme et/ou de conception.

Déjà vous avez un soucis côté cartographie, à priori vous avez des bâtiments, étages, couloirs, salles de classes.
Et déjà arriver à traduire la position GPS en "je suis dans le bâtiment A, 2ème étage, couloir central" n'est pas si trivial...
Après si on veut aller dans la classe X du bâtiment B, il va falloir un graphe qui répertorie les nœuds (emplacements) et les arcs (les divers chemins possibles).
Cartographie et graphe associés sont des sujets de conception (et il faut regarder l'état de l'art - ce que les autres font): peu importe le langage que vous aurez choisi, si vous ne savez pas comment vous allez représenter tout çà, vous ne serez pas plus avancé en disant "je veux coder en Python".

- W

Le graphe n'est pas un réel problème, la conception de mon lycée n'est pas très dure et j'ai préféré vulgariser en ne mettant que les couloirs/ halls... plutôt que de mettre précisément les salles pour commencer.
Le seul endroit complexe on va dire est le hall central (ici H) qui est lié à plusieurs sommets, mais pour le reste c'est plutôt classique. Bien sur les variables écrites pour les sommets sur ce schéma ne sont pas les bonnes, je vais les modifier, mais c'est une image du graphe auquel j'ai pensé pour l'algorithme.

Pièce jointe 461501

Citation:

---

Envoyé par Redelta

Le graphe n'est pas un réel problème, la conception de mon lycée n'est pas très dure et j'ai préféré vulgariser en ne mettant que les couloirs/ halls... plutôt que de mettre précisément les salles pour commencer.

---

Comment vous reliez les coordonnées GPS à votre graphe?
note: aller d'un point à un autre du graphe, vous ne savez peut être pas faire mais il y a des solutions que vous pouvez apprendre.... donc c'est "simple".

- W

Citation:

---

Envoyé par wiztricks

Comment vous reliez les coordonnées GPS à votre graphe?

---

Je ne comprend pas trop ce que vous essayez de me dire...

Elle nous a jamais fait de cours sur la notion de GPS, chemin le plus court... donc je dois pas mal me débrouiller seul et franchement je bloque parce que je ne sais pas vers où aller

Citation:

---

Envoyé par wiztricks

note: aller d'un point à un autre du graphe, vous ne savez peut être pas faire mais il y a des solutions que vous pouvez apprendre.... donc c'est "simple".

---

Je me doute que ça ne doit pas être très complexe mais pour ce projet du lycée, on est en quelque sorte "guidé" par notre prof et elle veut qu'on aille dans un sens bien précis, elle m'a demandé de représenter sous forme de matrice comme je l'ai dit mais pour le reste je ne sais pas trop... Elle nous a jamais fait de cours sur la notion de GPS, chemin le plus court... donc je dois pas mal me débrouiller seul et franchement je bloque parce que je ne sais pas vers où aller, la plupart des cours que je trouve sur internet me paraissent assez compliquer à aborder et je ne les comprend pas toujours...

Salut,

Si votre prof. a des idées pour simplifier ce qu'on peut imaginer avoir à coder pour réaliser ce genre d'application, c'est très bien mais on n'est pas dans sa tête!

- W

Bonsoir, excusez moi du temps de réponse, j'ai eu le temps de demander le nécessaire à ma professeur mais elle refuse de m'aider, elle dit qu'on doit se contenter de ses cours mais elle ne rentre jamais dans des types de code bien spécifique comme cet algorithme donc ça me bloque pas mal ce que je peux faire et j'ai donc pour seul outil internet. J'ai trouvé cette vidéo https://www.youtube.com/watch?v=CWVk0hIJH4U qui résume vraiment bien la représentation sur Python de cet algorithme, je pense grandement m'en inspirer, dans la vidéo ça nous montre l'ensemble des chemins qui partent d'un point spécifique sans point d'arrivé mais du coup je vais modifier pour faire en sorte qu'on choisisse un point d'arrivé également

Salut,

On trouve une foultitude de résultats avec "Python Dijkstra".

Par exemple:
http://isn.irem.univ-mrs.fr/2011-201...es/dijkstra.py
https://www.ljll.math.upmc.fr/pegon/...T/TP06_cor.pdf