Inscrivez-vous gratuitement
pour pouvoir participer, suivre les réponses en temps réel, voter pour les messages, poser vos propres questions et recevoir la newsletter
algorithme de Dijkstra
Bonsoir,
Notre prof d'info nous a fourni 2 versions de cet algorithme, mais je ne comprends pas les différences entre les 2, j'ai l'impression que ce sont deux choses totalement différentes ! Voici les programmes : http://myreader.toile-libre.org/uplo...d8ccd0c7e8.pdf
Quelles sont donc les différences entre les versions 1 et 2 ? Il y a un cas particulier puis un cas général ?
Merci beaucoup.
Salut,
L'algorithme de Dijkstra s'exprime d'abord en français et en pseudo code de "haut niveau".Envoyé par btpaoui
L'article de wikipedia vous décrit les différentes étapes.
Le prof vous a donné 2 implémentations. Une qui le réalise avec des listes de listes et des fonctions externes à la boucle principale, une autre qui profite des tableaux numpy et qui regroupe toutes les opérations à effectuer dans la boucle.
Donc après avoir testé que çà fonctionne pareil, à vous de décortiquer les deux codes pour vérifier qu'ils réalisent bien les différentes étapes de l'algo. Ce quoi vous aidera à comprendre la différence entre un algorithme et des réalisations/implémentations d'un algorithme (sa traduction en Python).
- W
Merci pour votre réponse.
Ce que je ne comprends pas, c'est ce que prend en argument l'algorithme de Dijkstra dans les 2 cas ? Que prennent-ils dans la version 1 et la version 2 ?
Merci beaucoup.
Là pour le coup, il n'y a rien à comprendre, juste (savoir) lire le code.
Et à priori, il suffit de remplacer Dijkstra par dijkstra dans "plus_court_chemin" pour passer de l'un à l'autre.
- W
Merci beaucoup pour votre réponse.
Et que dois prendre en argument la fonction de la version 2 ?
Et celle de la fonction 1 ?
C'est juste les mêmes.
Imaginez devoir lire des phrases en français, vous êtes à priori capable de repérer, articles, sujets, verbe, complément,... sans pour autant connaître le sens de différents mots. La structure d'une phrase suivra les mêmes règles quelque soit son sens.
En programmation, c'est pareil, fonctions, conditions, boucles,... c'est la grammaire de base. Après qu'on s'en serve pour raconter l'algorithme de Djikstra ou une autre histoire, on saura le lire à partir du moment où on sait reconnaître la structure.
Et pour y arriver, il faut juste prendre le temps d'apprendre.
- W
OK.
Pour la version 1, je n'ai pas compris le rôle de la fonction "relâcher".
Pourriez-vous me l'expliquer svp ? Sinon c'est bon pour ce qu'il y a avant.
Merci.
C'est à vous de le comprendre.
Partez d'un graphe plus simple/petit.
Visualisez le contenu d'Attribut à chaque étape (la commande print est là pour çà).
Essayez de comprendre comment ces changements d'états reflètent ceux de l'algo.
- W
Répondre avec citation
Partager