itinéraire le plus court

Pierrot, je m’excuse si mon message t’a offensé ; ce n’était pas le but. Pas besoin de supprimer ton compte pour fuir ou faire plaisir à quelques personnes.

Pour un message problématique, tu peux le « signaler » pour que la modération le masque. Mais, pour soi, je trouve plus simple et plus rapide d’éditer son message pour supprimer la partie problématique (et indiquer qu’on a modifié pour que le fil ne soit pas étrange pour les personnes qui viendront plus tard.)

Bonjour,

J’invite les participants à plus de tact dans leurs posts respectifs.

@PierrotLeFou Je ne crois pas qu’il soit nécessaire de vouloir supprimer son compte ou masquer ses posts (que j’ai rétabli afin de ne pas nuire à la lecture du sujet, même si le code fourni est problématique).

Je pense, au contraire, qu’une discussion honnête permettra tant à l’OP qu’aux autres intervenants de mieux comprendre le problème et les solutions éventuelles (et par extension, toutes les remarques sur le code que tu as fourni sont bonnes à prendre). La critique constructive n’est jamais une mauvaise chose et, si une réponse te semble problématique, signaler le post permettra — comme c’est le cas ici - à un membre du staff d’intervenir pour calmer le jeu mais il n’est pas nécessaire de partir dans la confrontation ou inversement, de fuir le débat. Les gens ne sont généralement pas méchants sur ZdS.

Je ne sais pas si je peux continuer ici …

Mon code avait effectivement des bugs:

• Je ne transmettais pas la valeur cumulée au sommet suivant.
• je faisait le parcours à partir du début pour trouver le chemin le plus court. Il faut le faire à partir de la fin vers le début.

Ensuite, il était inutile de retourner les longueurs minimales, puisqu’on retrouve dans acess cette valeur pour le sommet de sortie.

Pour des graphes orientés, je suppose qu’il ne faut pas enregistrer la distance dans les deux directions. Mais je devrais accumuler dans acces le sommet associé à la dernière valeur qu’on y a placée.

J’appelle toujours ma fonction dijkstra même si ce n’en est pas un. Voici mon nouveau code:

# Algorithme de Dijkstra.
def dijkstra(graphe, acces, cumulatif, sommet, sortie):
    if sommet == sortie: return
    for noeud, distance in graphe[sommet].items():
        if cumulatif + distance < acces[noeud]:
            acces[noeud] = cumulatif + distance
            dijkstra(graphe, acces, cumulatif+distance, noeud, sortie)
 
# 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.
dijkstra(graphe, acces, 0, sommet1, sommet2)
chemin = [sommet2]
minimum = acces[sommet2]
if minimum < float('inf'):
    print("La longueur du chemin minimum est", minimum)
    while sommet1 != sommet2:
        for sommet, distance in graphe[sommet2].items():
            if minimum - distance == acces[sommet]:
                chemin.append(sommet)
                sommet2 = sommet
                minimum -= distance
                break
    chemin.reverse()
    print(chemin)
else:
    print(f"Pas de chemin entre {sommet1} et {sommet2}")

Il semble que je ne comprenne pas bien l’algo de Dijkstra. Pour le petit graphe suivant:

a b 4
a c 5
b c 2
b d 9
c d 5
a d 0

La dernière ligne démarre l’algo et indique que 'a' est le début et 'd' est la fin.

Selon ma compréhension de l’algo, il ne devrait pas regarder les suivants de 'c' car c’est la branche 'a’->’b' qui est minimale. Et pourtant, il faut passer par 'c' pour un chemin minimal.

Avec ce graphe, l’algo de Dijkstra va se comporter grosso-modo de la façon suivante. On part de a, les points atteignables sont les suivants :

a > b: 4
a > c: 5

Le chemin le plus court est a > b, donc on se place en b et regarde ce qui se passe :

a > b: 4
    b > c: 6  # on rejette cette branche comme on peut atteindre `c` en 5.
    b > d: 13
a > c: 5

On sait déjà qu’on peut atteindre d en 13, voyons si on peut faire moins. La branche la plus courte est à présent a > c, donc on se place en c

a > b: 4
    b > d: 13
a > c: 5
    c > d: 10

On sait qu’on peut atteindre d en 10. On a aussi atteint d dans chacun des sous-graphes, donc on peut s’arrêter là, et on sait que la réponse est a > c > d: 10.

Je ne commente pas sur ton code comme c’est hors-sujet…

L’intérêt de Dijkstra est que si il y avait en plus un sommet e tel que a > e: 10 (par exemple), on ne considérerait jamais cette branche comme on a atteint la cible avec cette distance. Ou bien si on avait un sous-graphe dans ce genre :

a > e: 8
    e > f: 11
    e > g: 10
    e > h: 15

on irait jamais plus profondément que ce premier "sondage" de la branche a > e.

b > c: 6 # on rejette cette branche comme on peut atteindre c en 5.

Pour pouvoir rejeter cette branche, il a fallu qu’on se rendre jusqu’à c en passant par b. Donc, le noeud `c est visité plus d’une fois.

Pourqqoi Dijkstra demande qu’on assigne une valeur infinie comme distance initiale du début à chaque sommet si ce n’est pour comparer avec les autres sous-graphes se rendant à ce sommet.

Je pense que ce qui est important, ce n’est pas de visiter un sommet une seule fois, mais de parcourir un arc une seule fois.

Et je pense que c’est ce que fait mon code.

Pour pouvoir rejeter cette branche, il a fallu qu’on se rendre jusqu’à c en passant par b. Donc, le noeud c est visité plus d’une fois.

Ce que @ache voulait dire par "un nœud n’est visité qu’une seule fois" est qu’on itère sur les voisins d’un nœud donné qu’une seule fois (au plus). On peut évidemment arriver sur le même nœud plusieurs fois. Le choix de mots était pas judicieux, ça c’est sûr…

Pourquoi Dijkstra demande qu’on assigne une valeur infinie comme distance initiale du début à chaque sommet si ce n’est pour comparer avec les autres sous-graphes se rendant à ce sommet.

Cette astuce est justement pour pouvoir comparer aux autres visites, comme tu le dis. Personnellement je pense pas que ce soit si élégant que ça, ça empêche l’algorithme de fonctionner sur des types qui n’ont pas d’infini à disposition (les entiers par exemple, ou bien on pourrait même imaginer utiliser l’algorithme sur une mesure de distance un peu particulière qui demande son propre type et qui n’a pas d’infini). J’utiliserais plutôt une map pour conserver les chemins les plus cours connus jusqu’en chaque sommet, si le sommet est pas dans cette map c’est qu’on l’a pas encore rencontré (équivalent de la distance "infinie" utilisée dans certaines descriptions de l’algorithme).

Je pense que ce qui est important, ce n’est pas de visiter un sommet une seule fois, mais de parcourir un arc une seule fois.

Oui. @ache a mal choisi ses mots je pense, mais c’est effectivement ce que Dijkstra garanti.

Et je pense que c’est ce que fait mon code.

Encore une fois, vérifier ton code n’est pas le sujet de ce topic. C’est ce que je veux dire quand je dis que commenter sur ton code est hors-sujet. Il y a plusieurs raisons pour lesquelles le fait que tu as posté ton propre code a été mal reçu.

• Le but de ce forum n’est jamais de donner du code tout fait. On est là pour aider la personne qui a posé la question à comprendre comment arriver à une solution, pas lui donner la solution.
• Tu as posté une implémentation avant même que l’OP n’ait daigné nous donner une description claire de son projet, il est aussi de coutume sur ce forum que l’OP participe activement à la discussion et montre ses efforts avant que l’on offre des réponses détaillées.
• Le code que tu as posté n’est pas de bonne qualité, et ça c’est assez gênant. Si on doit débugger les codes des intervenants en plus de celui de l’OP, on s’en sort pas. Personnellement, j’ai arrêté de lire en détail quand j’ai vu que la fonction dijkstra modifie une de ses variables d’entrée d’une manière assez obscure (i.e. il faut lire le code pour comprendre ce qui est fait) au lieu de retourner le plus court chemin entre deux points (ce que l’algo de Dijkstra est sensé faire !).

Cela dit, vu que l’OP nous a fait faux-bond et qu’on ne le reverra sans doute même pas, autant utiliser ce sujet… Un problème assez clair avec ton programme en l’état et justement le fait que dijkstra implémente à moitié l’algo, puis que tu te visites le graphe une seconde fois (contraire donc à l’esprit de Dijkstra) pour retrouver le plus court chemin. Il n’y a aucune raison de faire ça, il est beaucoup plus simple de sauvegarder le chemin parcouru pendant l’exécution même de l’algorithme de Dijkstra.

Pour pouvoir rejeter cette branche, il a fallu qu’on se rendre jusqu’à c en passant par b. Donc, le noeud c est visité plus d’une fois.

Non, le nœud est visité (ou sélectionné si tu veux) au plus une seule fois. Mais ses arêtes peuvent être relaxées plus d’une fois (la mise à jour des distances). En sommes, dans mon idée, relaxer les arêtes d’un nœud ne nous fait pas “voyager”, on met seulement à jour les distances.

Je pense que ce qui est important, ce n’est pas de visiter un sommet une seule fois, mais de parcourir un arc une seule fois.

Oui si tu veux dans l’idée mais, c’est techniquement faux dans les graphes non orienté car dès que tu visites (ou sélectionne) un nouveau nœud (pas la source donc, ni la destination d’ailleurs), tu relaxes également l’arête qui t’a permis de venir depuis le nœud sélectionné précédent. Bref, techniquement, tu “parcoures” (ou visite, le terme est normalement « relexer ») un arc au maximum 2 fois avec Dijkstra.

Je trouve perso que le choix de l’infini est intéressant pour l’algo en elle-même… Ça oblige justement à bien comprendre au lieu de juste transposer : l’implémentation dans le langage choisi va alors forcément nécessiter une adaptation en terme de structure de données (même quand on a de l’infini à dispo, on n’est pas en train de faire du calcul formel… d’ailleurs me semble avoir déjà vu une implémentation qui utilisait des zéros.)

Un problème assez clair avec ton programme en l’état et justement le fait que dijkstra implémente à moitié l’algo, puis que tu te visites le graphe une seconde fois (contraire donc à l’esprit de Dijkstra) pour retrouver le plus court chemin.

Le problème claire est que Dijkstra sélectionne le nœud de distance minimum.

Cette histoire de parcourt n’est pas très choquant pour moi mais généralement on stocke le prédécesseur de chaque nœud. On retrouver ainsi le chemin en parcourant les prédécesseurs depuis le nœud de destination jusqu’à la source. Ça évite de parcourir toutes les arrêtes.

Un prédécesseur est le nœud depuis lequel on a mis à jour la distance. Il est mis à jour en même temps que la distance.

Le choix de mots était pas judicieux, ça c’est sûr…

L’algorithme de Dijkstra est fondé sur un parcourt en largeur et le terme « visiter » est le terme couramment utilisé pour le parcourt en largeur.

Par Wikipédia, par les cours à la fac et par ZdS. Je ne suis pas convaincu qu’on puisse dire qu’il est sûr que le choix du mot n’était pas judicieux. Je te laisse moinssoyer.

Oui si tu veux dans l’idée mais, c’est techniquement faux dans les graphes non orienté car dès que tu visites (ou sélectionne) un nouveau nœud (pas la source donc, ni la destination d’ailleurs), tu relaxes également l’arête qui t’a permis de venir depuis le nœud sélectionné précédent. Bref, techniquement, tu “parcoures” (ou visite, le terme est normalement « relexer ») un arc au maximum 2 fois avec Dijkstra.

??? On ne relaxe pas les arêtes, mais la distance qui permet d’atteindre un nœud donné. Le fait que le graphe soit orienté ou non ne change absolument rien en pratique, revenir au nœud (N) précédent à partir du nœud courant va forcément conduire à une distance plus grande pour atteindre ce nœud (N). De fait, l’arête en question n’est jamais considérée dans le sens de retour vers le nœud précédent.

La relaxation est une opération sur les arrêtes. Pas sur les distances.
C’est celle-ci dans le code de @PierrotLeFou.

if cumulatif + distance < acces[noeud]:
   acces[noeud] = cumulatif + distance

Si tu trouves une référence qui parle de relaxation des distances, tu peux m’en faire part si tu veux.

Bref, étant donné qu’une distance ne peut qu’augmenter, alors oui, si un arc mets à jour une distance dans un sens il ne le fera jamais dans l’autre sens dans l’algorithme de Dijkstra.

Le texte de Wikipedia n’est pas suffisamment clair (pour moi, en tout cas).

J’ai trouvé ce site qui explique mieux cet algorithme:

Algorithme de Dijkstra.

Le titre n’est pas très original, mais j’aime la présentation.

Le texte de Wikipedia n’est pas suffisamment clair (pour moi, en tout cas).

Oui, je peux comprendre. Wikipédia semble parfois un peu abrupt et dur à appréhender.

Le titre n’est pas très original, mais j’aime la présentation.

Je comprends, c’est pas mal en effet. Je viens de finir de le lire, il est agréable à lire.

@adri1: Tiens t’as vu, le site aussi il utilise le terme « visiter ». On a tous très mal choisi dis donc.

Par contre, on va arrêter avec les réponses sarcastiques, svp.

Il n’y a rien de bien méchant ou provocant dans ce que @adri1 a dit et, même si je peux concevoir que cela ait mal été interprété, ce genre de réponse ne peut mener qu’à une joute de piqûres écrites. Ce qui n’est ni désiré ni désirable.