Trouver le plus court chemin en utilisant l'algorithme de Dijkstra Exercice

On représente sur le graphe G ci-dessous les liaisons routières entre sept places (A, B, C, D, E, F,G) d'un centre-ville. Sur chaque route est indiqué le nombre de feux rouges présents entre les deux places qu'elle relie.

Un automobiliste souhaite emprunter le trajet comprenant le mois de feux tricolores pour se rendre de A à G.

Quel itinéraire cet automobiliste doit-il emprunter ?

A − B − D − G

A − C − E − F − G

A − C − D − G

A − C − E − D − G

On représente sur le graphe G ci-dessous les liaisons routières entre six villes (A, B, C, D, E, F). Sur chaque route est indiqué le temps de trajet (en minutes) entre les deux villes qu'elle relie.

Un automobiliste souhaite se rendre le plus rapidement possible de E à F.

Quel itinéraire cet automobiliste doit-il emprunter ?

E − D − C − F

E − A − B − F

E − D − B − F

E − A − D − C − F

Un automobiliste souhaite se rendre le plus rapidement possible de A à C.

Quel itinéraire cet automobiliste doit-il emprunter ?

A − E − D − F − C

A − B − D − C

A − E − B − D − F − C

A − E − D − C

On représente sur le graphe G ci-dessous les liaisons routières entre 8 villes (A, B, C, D, E, F, G, H). Sur chaque route est indiqué la distance en km entre les deux villes qu'elle relie.

Un automobiliste souhaite emprunter le trajet le plus court pour se rendre de A à F.

Quel itinéraire cet automobiliste doit-il emprunter ?

A − C − E − G − F

A − B − C - G − F

A − B − C − H − F

A − B − E − G − F

Un automobiliste souhaite se rendre le plus rapidement possible de E à C.

Quel itinéraire cet automobiliste doit-il emprunter ?

E − D − C

E − F − C

E − F − D − C

E − F − A − B − C