Outils pour utilisateurs
les_exposes:plus_court_chemin
Différences
Ci-dessous, les différences entre deux révisions de la page.
| Les deux révisions précédentes Révision précédente | Prochaine révision Les deux révisions suivantes | ||
|
les_exposes:plus_court_chemin [30/10/2016 18:53] paquier |
les_exposes:plus_court_chemin [30/10/2016 18:55] paquier |
||
|---|---|---|---|
| Ligne 47: | Ligne 47: | ||
| {{:les_exposes:545px-dijkstrabis05.svg.png?200|}} | {{:les_exposes:545px-dijkstrabis05.svg.png?200|}} | ||
| + | |||
| + | |||
| <-- la distance la plus courte en dehors du sous-graphe est maintenant celle de la ville C. On choisit donc C. On met à jour la ville G (403) et la ville H (320). | <-- la distance la plus courte en dehors du sous-graphe est maintenant celle de la ville C. On choisit donc C. On met à jour la ville G (403) et la ville H (320). | ||
| - | {{:les_exposes:545px-dijkstrabis06.svg.png?300|}} | + | {{:les_exposes:545px-dijkstrabis06.svg.png?200|}} |
| + | |||
| <-- la distance la plus courte en dehors du sous-graphe est maintenant celle de la ville H (320). On choisit donc H. On met à jour la ville D (503) et la ville J (487< 675). | <-- la distance la plus courte en dehors du sous-graphe est maintenant celle de la ville H (320). On choisit donc H. On met à jour la ville D (503) et la ville J (487< 675). | ||
| {{:les_exposes:545px-dijkstrabis07.svg.png?200|}} | {{:les_exposes:545px-dijkstrabis07.svg.png?200|}} | ||
| + | |||
| + | |||
| <-- la distance la plus courte suivante est celle de la ville G. On choisit G. La mise à jour ne change aucune autre distance. | <-- la distance la plus courte suivante est celle de la ville G. On choisit G. La mise à jour ne change aucune autre distance. | ||
| {{:les_exposes:545px-dijkstrabis08.svg.png?200|}} | {{:les_exposes:545px-dijkstrabis08.svg.png?200|}} | ||
| + | |||
| + | |||
| <-- la distance la plus courte suivante est celle de la ville I. La distance de la ville voisine J n'est pas modifiée car la distance existante est inférieure à celle que l'on obtiendrait en passant par I (415 + 84 > 487). | <-- la distance la plus courte suivante est celle de la ville I. La distance de la ville voisine J n'est pas modifiée car la distance existante est inférieure à celle que l'on obtiendrait en passant par I (415 + 84 > 487). | ||
| {{:les_exposes:545px-dijkstrabis09.svg.png?200|}} | {{:les_exposes:545px-dijkstrabis09.svg.png?200|}} | ||
| + | |||
| + | |||
| <-- la ville dont la distance est la plus courte est J (487). On choisit J et on l'ajoute au sous-graphe. On s'arrête puisque la ville d'arrivée est maintenant dans le sous-graphe. | <-- la ville dont la distance est la plus courte est J (487). On choisit J et on l'ajoute au sous-graphe. On s'arrête puisque la ville d'arrivée est maintenant dans le sous-graphe. | ||
les_exposes/plus_court_chemin.txt · Dernière modification: 02/11/2016 12:25 par paquier
Outils de la page
Sauf mention contraire, le contenu de ce wiki est placé sous les termes de la licence suivante : GNU Free Documentation License 1.3
