Accueil du site > MOCA > Chemins optimaux dans un graphe
Aller à ...
OMFG
Informations
Dans la rubrique MOCA , cet article a été écrit par b3nj et publié le 19 mars 2006.
3029 personnes ont affiché cette page et sa popularité est de 2.
Pebkac
Mots clefs
I see dead pixels.
Outils
SYN
Chemins optimaux dans un graphe

Introduction

PNG - 5.5 ko
Exemple de graphe orienté pour recherche de chemins optimaux

Le but est de rechercher le plus court chemin entre les sommets A et H.

Enumération des chemins :

\left( A, B, E, H \right) \rightarrow 19
\left( A, B, E, F, H \right) \rightarrow 20
\left( A, C, E, H \right) \rightarrow 20
\left( A, C, E, F, H \right) \rightarrow 21
\left( A, C, F, H \right) \rightarrow 12
\left( A, D, F, H \right) \rightarrow 11 \qquad \leftarrow Chemin de longueur minimale
\left( A, D, G, H \right) \rightarrow 19

Nous voyons donc que le plus court chemin est \mu = \left( A, D, F, H \right) et que l\left( \mu \right) = 11

pages : 1 2 3 4 >>
Poster un message