Plus court chemin dans un graphe non orienté


Recherche du plus court chemin

Algorithme de Dijkstra.

Les sommets du graphe non orienté et sans boucles, sont A, B, C, ..., H


Le programme va déterminer la valeur du plus court chemin entre deux sommets donnés du graphe, tout en détaillant la progression des calculs, permettant ainsi de comprendre l'algorithme utilisé.

Entrez les valeurs positives associées des arêtes du graphe. (lorsqu'il n'y a pas d'arête entre deux sommets laissez la case vide).
Plus bas dans la page, plusieurs exemples de graphes sont dessinés et préprogrammés, en peu de clics, sans rien écrire, ils sont exécutés, la figure permet de visualiser la solution obtenue du plus court chemin.



Remarques

Si on ne modifie pas les données, ce programme permet en particulier de résoudre l'activité 11 (page 276 du livre de Maths de T.E.S.), dont le graphe est représenté sur la première des figures visibles ci-dessous. D'autres exercices sont disponibles en cliquant.



En changeant les données, lorsque le nombre de sommets du graphe ne dépasse pas 8, cette page permet de résoudre n'importe quelle recherche de plus court chemin.

Liens

Plus court chemin   Graphes, orientés ou non, d'un nombre quelconque de sommets.



L'algorithme est de Dijkstra.
Edsger Dijkstra est né à Rotterdam en 1930 et est décédé le 6 Août 2002.
En France l'algorithme est attribué conjointement à Moore et à Dijkstra et est appelé « algorithme de Moore-Dijkstra ».
J. Strother Moore enseigne à l'université d'Austin au Texas.
J. S. Moore est avec Robert Stephen Boyer l'un des auteurs de NQTHM, un programme permettant de démontrer des théorèmes.
Boyer et Moore sont aussi les inventeurs de l'algorithme le plus rapide connu de recherche de sous-chaînes dans une chaîne de caractères (recherche des occurrences d'un mot dans un phrase ou dans un texte).

Faites Ctrl-F (ou Alt-F avec Netscape 4.7), dans la fenêtre qui s'ouvre écrivez un mot, lancez ensuite sa recherche dans cette page, à ce moment là vous utilisez sans doute l'algorithme de Boyer-Moore.
















Pour un premier contact, [utilisez ce formulaire] ou utilisez l'adresse de messagerie qui y figure. Merci d'indiquer la page précise du site "http//jm.davalan.org/...", cela m'aidera beaucoup. Ne joignez aucun document à votre message.
Jeux-et-Mathématiques n'est pas un site commercial. Aucun des liens placés sur ce site n'est rémunéré, ni non plus aucune des informations données.
Important : Si votre question a un quelconque rapport avec un travail personnel (Devoir TIPE Master...) , vous devez absolument me le préciser dès votre premier message et m'indiquer très précisément les limites des informations demandées. Vous devez aussi avertir la personne qui dirige éventuellement votre travail ou le corrige de cette communication et lui montrer les documents fournis.

J'essaie de répondre aux questions posées, mais ne lis pas les documents mathématiques amateurs, pas plus que je ne donne mon avis sur les démonstrations des conjectures de Collatz ou autres. Je ne lis pas les documents word, je ne corrige pas les programmes informatiques et depuis des années je n'utilise plus de tableur.

© (Copyright) Jean-Paul Davalan 2002-2014