Algorithme de Dijkstra

samedi 27 septembre 2008
popularité : 1%

GIF - 16.6 ko

L’exercice consiste à trouver le (ou les) plus court(s) chemin(s) (de longueur µ) entre les sommets E et S en utilisant l’ algorithme de Dijkstra. Le graphe est orienté et pondéré par des coefficients n[1] à n[8] (compris entre 1 et 11) .

On peut utiliser cet exercice pour déterminer les valeurs des coefficients n[i] de telle façon que le nombre n de plus courts chemins soit égal à 2, 3, 4 ou 5.

Ceci revient à résoudre des système linéaires.

Exemple : n = 3.

Pour que les 3 chemins (EABS), (ECABS) et (ECDS) aient même longueur µ, il suffit de réaliser : n[1] + n[4] + n[5] = n[2] + n[3] + n[4] + n[5] = n[2] + n [7] + n[8].

Niveau : Terminale E.S.

Logiciel : GeoplanW (version 2)


Documents joints

GeoPlan - 19.3 ko
GeoPlan - 19.3 ko
Word - 31.5 ko
Word - 31.5 ko