itinéraire le plus court

Bonjour, je suis actuellement en première et je fait la spé nsi. Nous sommes en plein projet de fin d’année, et mon projet est le suivant : créer un programme qui trouve l’itinéraire le plus court entre 2 points donnés par l’utilisateur. Pour cela, pour faire rapide, nous utilisons l’algorithme de dijkstra(ou chaque intersections de rue est un sommet), or pour utiliser cet algo il faut pouvoir savoir quel sommet a accès à quel sommet (un graph quoi). Cependant quand l’utilisateur rentre les coordonnées du point de départ ou d’arrivé on ne sait pas à quel sommet il a accès. Au début nous avons fait une fonction qui part du principe que le sommet le plus proche est atteignable cependant ce n’est pas toujours le cas (rues parallèles proches par exemple). Nous avons beaucoup réfléchis mais sans résultat alors j’aimerai savoir si vous aviez des idées. Cdt Gabriel

Je ne vois pas beaucoup d’autres choix que de se baser sur une carte.

J’imagine que le plus simple serait de se baser sur les cartes d’OpenStreetMap dont les informations de rues et d’intersection sont disponibles sur Internet.

Donc j’abandonnerai l’idée avec l’algo de dijkstra ?

Salut,

Trouver le plus court chemin entre deux points arbitraires sur Terre est un peu raide pour un sujet de NSI… Ou alors ça se résume à appeler l’API d’une appli qui fait déjà ça, et ça devient pas très intéressant. Tu pourrais peut être te concentrer sur une région connue/arbitraire (genre un étage de ton école ou même un lieu fictif simple) pour laquelle il serait possible de définir le graphe de nœuds et de distances à la main sans y passer des heures. Ça pourrait même être un labyrinthe généré aléatoirement. Je pense que dans le cadre de ce projet, le but est de coder l’algo de recherche plutôt que se casser les dents pour récupérer un graphe qui représente les rues sur une carte réelle à partir d’OpenStreetMap (même à l’échelle d’une petite ville, ça peut être délicat !).

Salut,

Pour avoir travaillé sur un GPS. Il te faut connaître un maximum de routes et utiliser l’algorithme de Dijkstra.

Pour le début de l’itinéraire, il faut en effet chercher à rejoindre l’axe le plus proche. Et comme vous l’avez bien détecté, ça n’est pas simple, c’est même impossible! Par exemple, on peut détecter qu’il y a une route à 20 mètres et essayer de la rejoindre, mais peut-être qu’une rivière nous sépare de cette route. Tenter de guider vers elle, amène à une situation ubuesque! Le moyen utilisé était une étude du comportement du véhicule, pour décider de guider vers un autre axe. La fin de l’itinéraire pose le même problème, avec plus de pièges! Ensuite se pose un problème d’optimisation du temps de calcul, là il suffit d’ôter toutes les "petites" routes qui ne sont pas "proches" du départ et de la destination. Par exemple si on va de Paris à Marseille, il y a peu de chance de passer par une petite rue de Dijon, mais l’autoroute A1 reste plausible! L’algorithme de Dijkstra peut être optimisé en utilisant divers euristiques. Pour reprendre le trajet Paris Marseille, envisager une route rennaise est à rejeter. On le détecte par une pré-estimation de de durées min/max plausibles du trajet (p.e on trouve 4h pour Paris/Rennes + dist(Rennes/marseille)/105km/h > dist(Paris/Marseille)/60km/h)

Je suppose qu’il s’agit d’un chemin fictif et non un de ceux mentionnés ci-haut …

J’ai déjà fait un Dijkstra avec un dictionnaire de dictionnaires en Python.

Quand on a une paire de sommet et la longueur (ou distance) qui les sépare, on ajoute à chacun des deux une entrée dans le sous-dictionnaire de l’autre.

Les clés du dictionnaire principal sont des noeuds, de même que pour les dictionnaires secondaires.

Les valeurs du dictionnaire principal sont le sous-dictionnaire des noeuds adjacents à chaque noeud.

Et les valeurs des entrées des sous-dictionnaires sont la distance entre les deux, et de la distance du début sous forme de liste.

Ça pourrait avoir l’air de ceci

graphe = {'a': {'b': [5, float('inf')], 'c': [7, float('inf')], ...}, 'b': {...}, ...}

Noter que float('inf') représente l’infini mais peut être utilisé dans les comparaisons.

Il faut bien sûr connaître le noeud de départ et le noeud d’arrivée. Et rien ne dit qu’on va se rendre du début à la fin. Si l’algorithme retourne au début une longueur infinie, c’est qu’il n’y a pas de chemin entre les deux.

Note:

J’ai laissé le début …

Il ne faut associer à chaque noeud qu’un seul- minimum donnant la longueur du sous-chemin minimum pour s’y rendre.

Pourquoi ça ?
Non c’est pas du tout ce que j’ai dis.

Mais votre consigne est très mal présentée. Je cite le problème :

créer un programme qui trouve l’itinéraire le plus court entre 2 points donnés par l’utilisateur.

Si je devais répondre, je dirais que c’est pas un problème. Le chemin le plus cours entre deux points c’est le segment qui lie ces deux points.

À partir du reste du message, on en a déduit qu’on vous avait donné un graphe. Manifestement, ce n’est pas le cas ? Vous parlez de rue dans votre problème mais ça sort un peu de nul-part.

Juste pour avoir un graphe avec des rues, se baser sur OpenStreetMap me semble une bonne idée. Après, c’est complexe et hors de porter d’un projet NSI.

Comme @adr1 le recommande, commencer par un graphe à la main. Un petit graphe, puis de taille moyenne ensuite et éventuellement un truc plus compliqué. Le petit graphe, c’est l’étape première absolument nécessaire.

Tout projet est un processus itératif, commencez par ça déjà et ensuite quand vous aurez un truc fonctionnel vous l’améliorerez.

Je pense que gab.iwiban faisait allusion à des sous-graphes du genre quand il parle de rues:

a -> b

c -> d

qui ne se rencontrent pas.

Je maintiens mon idée qu’un Dijksttra se fait en Python avec un dictionnaire de dictionnaires.

Je donnerai mon code en temps voulu.

Voici l’allure définitive de ce que ça donne:

{'a': {'': 0, 'b': 3, 'c': 7}, 'b': {'': inf, 'a': 3, 'c': 3}, 'c': {'': inf, 'b': 3, 'a': 7}}                          

La clé "" est la distance minimale au noeud à une étape donnée.

Je maintiens mon idée qu’un Dijksttra se fait en Python avec un dictionnaire de dictionnaires.

Pourquoi veux-tu absolument utiliser un dictionnaire de dictionnaire ?
C’est pas le sujet il me semble et Python n’impose pas de structure de donnée particulière.

En NSI, ce qu’on apprend pour stocker un graphe, c’est:

1. La matrice d’adjacence.
2. Le stockage d’une liste de nœuds et une liste de successeur de chaque nœud. Que j’implémenterais effectivement avec dictionnaire de dictionnaire afin d’avoir un poids sur les arcs mais ton implémentation utilise un nœud '' qui n’a pas d’intérêt à part mélanger un peu tout.

Ici, tu mélanges la représentation du graphe avec un structure de donnée interne à l’algorithme. Utilise un autre dictionnaire pour ça afin de séparer les choses. Le graphe est une entrée, «la distance minimale au nœud» est une structure de donnée utilisée par l’algorithme.
Aussi, ce n’est pas la structure idéale pour l’algorithme de Dijkstra. On préfère une file de priorité pour déterminer le prochain nœud à visiter.

Je pense que gab.iwiban faisait allusion à des sous-graphes du genre quand il parle de rues:

Il va falloir qu’il explique mieux son problème.

Une matrice d’adjacence contient en principe N² élements, où N est le nombre de noeuds. Pour connaître tous les noeuds (plutôt arcs) sortants d’un noeud, il faut parcourir une ligne (ou colonne) d’une matrice en général presque vide.

Avec un dictionnaire, on a un accès plus rapide aux noeuds suivants. En plus un dictionnaire permet directement d’avoir des clés alphanumériques sans passer par une table de conversion.

Je suis d’accord que ma clé en chaîne vide n’est pas très élégante, mais je voulais tout garder dans la même structure sans que ça soit trop compliqué. Je ne voulais pas des choses du genre:

'nom': [distance_minimale, {... dictionnaire des noeuds suivants ...]}

J’aurais pu avoir un autre dictionnaire donnant la distance au début pour chaque noeud, mais ça faisait un paramètre de plus à passer à la fonction.

Aussi, ce n’est pas la structure idéale pour l’algorithme de Dijkstra. On préfère une file de priorité pour déterminer le prochain nœud à visiter.

C’est pour un parcours en largeur. Il faut maintenir cette file, probablement dans une liste. Ça évite sans doute d’avoir un algo récursif comme je le fais.

Note: je ne suis pas en France et je ne sais pas ce qu’on apprend en MSI.

Ces considérations de design sont complètement prématurées. On ne connait même pas le projet précis, si ça se trouve le design est déjà décidé et imposé. On ne connait pas non plus la taille du problème à résoudre, si ça se trouve il n’y a que quelque dizaines de nœuds à tout casser et à ce moment là prédire quelle approche aura effectivement les meilleurs performances devient à la fois difficile et surtout complètement inutile parce que le temps d’exécution sera majoritairement passé à démarrer la VM Python. De toutes façons, ça m’étonnerait fortement que les performances soient le cœur des préoccupations en NSI…

Salut ! j’ai du mal m’exprimer mais mon problème était écrit à la fin de mon message, le début était pour vous donner un peu de contexte. Mon problème était que je n’arrivais pas à savoir comment faire pour savoir quel est l’intersection(sommet si on généralise à un graph) la plus proche mais atteignable depuis le point de départ. Comme l’a dit dalfab l’intersection "la plus proche" ne signifie pas forcément qu’elle est atteignable, il peut y avoir une rivière entre le point et l’intersection la plus proche par exemple. Finalement j’ai trouvé une autre solution mais merci quand même pour votre aide. Cdt Gabriel

Ce que dalfab a indiqué correspond un peu à la crainte évoquée par adri1 ; et ce genre de complexité ne semble pas demandé dans le problème posé ni souhaitable pour ce type d’exercice. D’où l’invitation à partir de cas plus simples (et je trouve bien de générer des labyrinthes en prime, sinon tu peux prendre des plans très simples —par exemple le bahut ou une des ces villes en quadrillage) : le but est de vous faire travailler l’algo de Dijkstra, pas les problèmes annexes qui annexes qui occupent des armées d’ingénieurs à longueur de journées.

Pas besoin d’un exemple compliqué. Celui de Wikipedia sera suffisant:

Algorithme de Dijkstra — Wikipédia.

Je vous donne ma version de l’algorithme au cas où ça servirait à quelqu’un.

On donne en entrée sur chaque ligne les noms de deux sommets suivi de la distance qui les sépare (un int). La dernière ligne contient respectivement les noms de l’entrée, de la sortie et soit 0, soit un nombre négatif.

Je ne vérifie pas l’intégrité des données. Je laisse aux intéressés le soin de le faire.

J’ai finalement utilisé un dictionnaire (acces) qui donne la distance minimale à partir du début jusqu’à chaque sommet au moment présent.

# Algorithme de Dijkstra.
def dijkstra(graphe, acces, cumulatif, sommet, sortie):
    if sommet == sortie: return cumulatif
    minimum = float('inf')
    for noeud, distance in graphe[sommet].items():
        if cumulatif + distance < acces[noeud]:
            acces[noeud] = cumulatif + distance
            trajet = dijkstra(graphe, acces, distance, noeud, sortie)
            if trajet < minimum:
                minimum = trajet
    return cumulatif+minimum
 
# Saisie des données.
graphe = {}
acces = {}
while True:
    sommet1, sommet2, distance = input("> ").split()
    distance = int(distance)
    if distance <= 0: break
    acces[sommet1] =float('inf')    
    acces[sommet2] = float('inf')
    if sommet1 not in graphe.keys():
        graphe[sommet1] = {}
    graphe[sommet1][sommet2] = distance
    if sommet2 not in graphe.keys():
        graphe[sommet2] = {}
    graphe[sommet2][sommet1] = distance
acces[sommet1] = 0
 
# Retrouver le plus court chemin.
chemin = [sommet1]
minimum = dijkstra(graphe, acces, 0, sommet1, sommet2)
if minimum < float('inf'):
    print("La longueur du chemin minimum est", minimum)
    cumulatif = 0
    while sommet1 != sommet2:
        for sommet, distance in graphe[sommet1].items():
            if cumulatif + distance == acces[sommet]:
                chemin.append(sommet)
                sommet1 = sommet
                cumulatif += distance
                break
    print(chemin)
else:
    print(f"Pas de chemin entre {sommet1} et {sommet2}")

@PierrotLeFou: Ton algorithme est une exploration exhaustive qui n’a rien à voir avec Dijkstra et n’a aucune chance de fonctionner un graphe de grande taille.

La garantie de l’algorithme de Dijkstra est simple, ne visiter un nœud qu’une seule fois. Ici, tu n’as pas cette garantie. C’est la seule garantie de Dijkstra, et celle qui lui permet d’être efficace.

En plus, je soupçonne qu’il soit bugué.

Je suis déjà pas à l’aise avec l’idée de donner un code source complet mais je suis catégoriquement contre le fait de donner un code source faux.

L’exploration n’est pas hexaustive. Si je compare la valeur associée à la distance déjà marquée avec la distance cumulée courante, je ne vais pas plus loin dans cette direction.

Tu soupçonnes que ma version est buggée, as-tu un exemple ou peux-tu me pointer un endroit où ça risque de bugger?

Je vais tout de même revoir l’algo de Dijkstra …

J’ai pas le temps de chercher plus. J’ai un 40h par semaine et j’ai des cours à réviser.

Ton exploration est exhaustive car tu parcours tous les nœuds et tous les chemins au moins une fois.
Ce qui n’est bien-sûr pas le cas de l’algorithme de Dijkstra.

Exemple de graphe où ça marche pas:

graph = {
    'A': {
        'B': 3,
        'C': 2,
        'D': 1,
    },
    'B': {
        'A': 3,
        'E': 1
    },
    'C': {
        'A': 2,
        'E': 1
    },
    'D': {
        'A': 1,
        'E': 1
    },
    'E': {
        'B': 1,
        'C': 1,
        'D': 1,
        'F': 2,
        'G': 1,
    },
    'F': {
        'E': 2,
        'H': 1
    },
    'G': {
        'E': 1,
        'H': 1
    },
    'H': {
        'F': 1,
        'G': 1
    }
}

Le chemin le plus court entre 'A' et 'H' est assez simple à trouver à la main. Idem entre 'A' et 'G' et pourtant l’algorithme ne marche pas dessus.

Aussi, ton algorithme ne marche pas sur les graphes orienté alors que encore une fois, l’algorithme de Dijkstra fonctionne sur les graphes orientés.

PS: Je te recommanderais de créer un sujet pour tes problèmes et de retirer ton code de ce sujet.

PPS: exhaustive. Le 'h' est entre le x et le a.

Je ne sais pas comment supprimer mes messages.

Comment supprimer mon compte de ce forum?

Attends attends. Tout le monde fait des erreurs.

J’en fais pleins ! T’inquiète on peut éditer c’est rien.

C’est en faisant des erreurs qu’on apprend. J’ai beaucoup appris …

Edit: Tu peux masquer tes messages un bouton proche du message, je suis pas sûr, j’ai des droits de modération (¯_(ツ)_/¯). Il y a également une option pour supprimer un compte dans les “Paramètres”, champ “Désinscription”. Mais très franchement, y aucune raison d’en arriver là. Si j’ai l’air un peu dur, je m’en excuse. On a parfois des têtes bullées qui s’entêtent à en faire rire les mules.

Aussi pour être totalement franc, je comprends pas pourquoi le code marche pas.
J’ai pas le temps d’investiguer mais j’aimerais bien comprendre, d’où le fait que je t’invite à recréer un sujet pour en parler.