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

Un automobiliste souhaite se rendre de B à D en empruntant le trajet comportant le moins de feux tricolores possible.

Quel itinéraire cet automobiliste doit-il emprunter ?

D− E − F − B

F − B − D − E

A − C − B − D

B − F − E − D

On utilise l'algorithme de Dijkstra afin de rechercher la plus courte chaîne du graphe pondéré des temps de parcours.

On consigne les étapes dans un tableau. L'ordre des sommets dans le tableau n'a pas d'importance. On affecte le sommet de départ B d'un poids égal à 0, les autres étant affectés d'un poids infini :

B	A	C	E	F	D
0	\infty	\infty	\infty	\infty	\infty

Une fois un sommet traité, on grise verticalement le reste de la colonne.

On garde la dernière colonne afin de noter le sommet fixé à chaque étape.

Etape 1

Première étape

On part de B. Les sommets A, C, E et F sont adjacents à B. On écrit les poids correspondants avec, en indice, le sommet d'origine. Les autres sommets ont un poids infini.

B	A	C	E	F	D
0	\infty	\infty	\infty	\infty	\infty	B
	2_B	5_B	4_B	2_B	\infty

Etape 2

Deuxième étape

On choisit comme nouveau sommet celui atteint avec un poids minimal, c'est-à-dire ici A ou F, on choisit A arbitrairement et on remplit une nouvelle ligne.

B est adjacent à A mais sa colonne est déjà grisée.

E est adjacent à A :

De A à E, on a 3, auquel s'ajoute 2, on devrait donc inscrire 5_A mais 4_B étant inférieur on laisse ce dernier.

F et C ne sont pas adjacents à A, on réécrit donc respectivement 2_B et 5_B.

Le sommet D n'est pas adjacent à A, on réécrit donc \infty.

B	A	C	E	F	D
0	\infty	\infty	\infty	\infty	\infty	B
	\textcolor{Red}{2_B}	5_B	4_B	2_B	\infty	A
		5_B	4_B	2_B	\infty

Etape 3

Troisième étape

On choisit comme nouveau sommet celui atteint avec un poids minimal, c'est-à-dire ici F et on remplit une nouvelle ligne.

B est adjacent à F mais sa colonne est déjà grisée.

C, D et E sont adjacents à F :

De F à C, on a 4, auquel s'ajoute 2, on devrait donc inscrire 6_F mais 5_B est inférieur, on laisse donc ce-dernier.
De F à D, on a 5, auquel s'ajoute 2, on inscrit donc 7_F.
De F à E, on a 2, auquel s'ajoute 2, cela donne 4_F qui est égal à 4_B mais on note 4_F (cela nous permettra par la suite de déterminer l'itinéraire le plus court).

B	A	C	E	F	D
0	\infty	\infty	\infty	\infty	\infty	B
	\textcolor{Red}{2_B}	5_B	4_B	2_B	\infty	A
		5_B	4_B	\textcolor{Red}{2_B}	\infty	F
		5_B	4_F		7_F

Etape 4

Quatrième étape

On choisit comme nouveau sommet celui atteint avec un poids minimal, c'est-à-dire ici E et on remplit une nouvelle ligne.

E est adjacent à A, B et F mais leur colonne est déjà grisée.

D est adjacent à E :

De E à D, on a 2, auquel s'ajoute 4, on inscrit donc 6_E.

E n'est pas adjacent à C, on réécrit donc 5_B.

B	A	C	E	F	D
0	\infty	\infty	\infty	\infty	\infty	B
	\textcolor{Red}{2_B}	5_B	4_B	2_B	\infty	A
		5_B	4_B	\textcolor{Red}{2_B}	\infty	F
		5_B	\textcolor{Red}{4_F}		7_F	E
		5_B			6_E

Etape 5

Cinquième étape

On choisit comme nouveau sommet celui atteint avec un poids minimal, c'est-à-dire ici C et on remplit une nouvelle ligne.

D est adjacent à C :

De C à D, on a 2, auquel s'ajoute 5, on devrait donc inscrire 7_C mais on laisse 6_E car il est inférieur.

Les autres sommets sont déjà grisés.

B	A	C	E	F	D
0	\infty	\infty	\infty	\infty	\infty	B
	\textcolor{Red}{2_B}	5_B	4_B	2_B	\infty	A
		5_B	4_B	\textcolor{Red}{2_B}	\infty	F
		5_B	\textcolor{Red}{4_F}		7_F	E
		\textcolor{Red}{5_B}			6_E	C
					\textcolor{Red}{6_E}	D

Pour obtenir l'itinéraire le plus court, on effectue le trajet à l'envers en partant de la dernière ligne du tableau :

6_E indique qu'on vient du point E
on va chercher sur la colonne E la dernière case (4_F) qui nous indique que l'on vient du point F
on va chercher sur la colonne F la dernière case (2_B) qui nous indique que l'on vient du point B, qui est notre point de départ

L'itinéraire comportant le moins de feux tricolores est B - F - E - D, il y a 6 feux.

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

Un automobiliste souhaite se rendre de A à F en empruntant le trajet comportant le moins de feux tricolores possible.

Quel itinéraire cet automobiliste doit-il emprunter ?

F-C-E-D-B-A

A-B-E-D-C-F

A-B-C-D-E-F

A-B-F-E-C-D

On utilise l'algorithme de Dijkstra afin de rechercher la plus courte chaîne du graphe pondéré des temps de parcours.

On consigne les étapes dans un tableau. L'ordre des sommets dans le tableau n'a pas d'importance. On affecte le sommet de départ A d'un poids égal à 0, les autres étant affectés d'un poids infini :

A	B	C	D	E	F
0	\infty	\infty	\infty	\infty	\infty

Une fois un sommet traité, on grise verticalement le reste de la colonne.

On garde la dernière colonne afin de noter le sommet fixé à chaque étape.

Etape 1

Première étape

On part de A. Les sommets B et E sont adjacents à A. On écrit les poids correspondants avec, en indice, le sommet d'origine. Les autres sommets ont un poids infini.

A	B	C	D	E	F
0	\infty	\infty	\infty	\infty	\infty	A
	3_A	\infty	\infty	5_A	\infty

Etape 2

Deuxième étape

On choisit comme nouveau sommet celui atteint avec un poids minimal, c'est-à-dire ici B et on remplit une nouvelle ligne.

B est adjacent à A mais sa colonne est déjà grisée.

C et E sont adjacents à B :

De B à C, on a 11, auquel s'ajoute 3, on inscrit donc 14_B.
De B à E, on a 2, auquel s'ajoute 3, on inscrit donc 5_B.

D et F ne sont pas adjacents à B, on réécrit donc \infty.

A	B	C	D	E	F
0	\infty	\infty	\infty	\infty	\infty	A
	\textcolor{Red}{3_A}	\infty	\infty	5_A	\infty	B
		14_B	\infty	5_B	\infty

Etape 3

Troisième étape

On choisit comme nouveau sommet celui atteint avec un poids minimal, c'est-à-dire ici E et on remplit une nouvelle ligne.

A et B sont adjacents à E mais leur colonne est déjà grisée.

C et D sont adjacents à E :

De E à C, on a 6, auquel s'ajoute 5, on inscrit donc 11_E car ce dernier est inférieur à 14_B.
De E à D, on a 3, auquel s'ajoute 5, on inscrit donc 8_E.

Le sommet F n'est pas adjacent à E, on réécrit donc \infty.

A	B	C	D	E	F
0	\infty	\infty	\infty	\infty	\infty	A
	\textcolor{Red}{3_A}	\infty	\infty	5_A	\infty	B
		14_B	\infty	\textcolor{Red}{5_B}	\infty	E
		11_E	8_E		\infty

Etape 4

Quatrième étape

On choisit comme nouveau sommet celui atteint avec un poids minimal, c'est-à-dire ici D et on remplit une nouvelle ligne.

D est adjacent à E mais sa colonne est déjà grisée.

C et F sont adjacents à D :

De D à C, on a 2, auquel s'ajoute 8, on inscrit donc 10_D.
De D à F, on a 8, auquel s'ajoute 8, on inscrit donc 16_D.

A	B	C	D	E	F
0	\infty	\infty	\infty	\infty	\infty	A
	\textcolor{Red}{3_A}	\infty	\infty	5_A	\infty	B
		14_B	\infty	\textcolor{Red}{5_B}	\infty	E
		11_E	\textcolor{Red}{8_E}		\infty	D
		10_D			16_D

Etape 5

Cinquième étape

On choisit comme nouveau sommet celui atteint avec un poids minimal, c'est-à-dire ici C et on remplit une nouvelle ligne.

F est adjacent à C :

De C à F, on a 4, auquel s'ajoute 10, on inscrit donc 14_C car ce dernier est inférieur à 16_D.

Les autres sommets sont déjà grisés.

A	B	C	D	E	F
0	\infty	\infty	\infty	\infty	\infty	A
	\textcolor{Red}{3_A}	\infty	\infty	5_A	\infty	B
		14_B	\infty	\textcolor{Red}{5_B}	\infty	E
		11_E	\textcolor{Red}{8_E}		\infty	D
		\textcolor{Red}{10_D}			16_D	C
					\textcolor{Red}{14_C}	F

Pour obtenir l'itinéraire le plus court, on effectue le trajet à l'envers en partant de la dernière ligne du tableau :

14_C indique qu'on vient du point C
on va chercher sur la colonne C la dernière case (10_D) qui nous indique que l'on vient du point D
on va chercher sur la colonne D la dernière case (8_E) qui nous indique que l'on vient du point E
on va chercher sur la colonne E la dernière case (5_B) qui nous indique que l'on vient du point B
on va chercher sur la colonne B la dernière case (3_A) qui nous indique que l'on vient du point A, qui est notre point de départ

L'itinéraire comportant le moins de feux tricolores est A-B-E-D-C-F, il y a 14 feux.

On représente sur le graphe ci-dessous les liaisons ferroviaires entre sept gares (A, B, C, D, E, F, G). Sur chaque ligne est indiqué le temps de trajet en minutes (correspondance comprise) entre les deux gares qu'elle relie.

Un usager souhaite se rendre le plus rapidement possible de B à G.

Quel itinéraire cet automobiliste doit-il emprunter ?

B-C-D-F-G

B-C-D-A-F

B-C-D-A-G

G-F-D-C-B

On utilise l'algorithme de Dijkstra afin de rechercher la plus courte chaîne du graphe pondéré des temps de parcours.

B	A	C	D	E	F	G
0	\infty	\infty	\infty	\infty	\infty	\infty

Une fois un sommet traité, on grise verticalement le reste de la colonne.

On garde la dernière colonne afin de noter le sommet fixé à chaque étape.

Etape 1

Première étape

On part de B. Les sommets A, C,D et E sont adjacents à C. On écrit les poids correspondants avec, en indice, le sommet d'origine. Les autres sommets ont un poids infini.

B	A	C	D	E	F	G
0	\infty	\infty	\infty	\infty	\infty	\infty	B
	4_B	7_B	17_B	21_B	\infty	\infty

Etape 2

Deuxième étape

On choisit comme nouveau sommet celui atteint avec un poids minimal, c'est-à-dire ici A et on remplit une nouvelle ligne.

B est adjacent à A mais sa colonne est déjà grisée.

C est adjacent à A :

De A à C, on a 8, auquel s'ajoute 4, on devrait donc inscrire 12_A mais 7_B étant inférieur on laisse ce dernier.

D n'est pas adjacent à A, on réécrit donc 17_B.

E n'est pas adjacent à A, on réécrit donc 21_B.

Les sommets F et G ne sont pas adjacents à A, on réécrit donc \infty.

B	A	C	D	E	F	G
0	\infty	\infty	\infty	\infty	\infty	\infty	B
	\textcolor{Red}{4_B}	7_B	17_B	21_B	\infty	\infty	A
		7_B	17_B	21_B	\infty	\infty

Etape 3

Troisième étape

On choisit comme nouveau sommet celui atteint avec un poids minimal, c'est-à-dire ici C et on remplit une nouvelle ligne.

A et B sont adjacents à C mais leur colonne est déjà grisée.

D et F sont adjacents à C :

De C à D, on a 10, auquel s'ajoute 7, on inscrit donc 17_C.
De C à F, on a 25, auquel s'ajoute 7, on inscrit donc 32_C.

E n'est pas adjacent à C, on réécrit donc 21_B.

Le sommet G n'est pas adjacent à D, on réécrit donc \infty.

B	A	C	D	E	F	G
0	\infty	\infty	\infty	\infty	\infty	\infty	B
	\textcolor{Red}{4_B}	7_B	17_B	\infty	\infty	\infty	A
		\textcolor{Red}{7_B}	17_B	21_B	\infty	\infty	C
			17_C	21_B	32_C	\infty

Etape 4

Quatrième étape

On choisit comme nouveau sommet celui atteint avec un poids minimal, c'est-à-dire ici D et on remplit une nouvelle ligne.

D est adjacent à B et à C mais leur colonne est déjà grisée.

E, F et G sont adjacents à D :

De D à E, on a 15, auquel s'ajoute 17, on devrait donc inscrire 32_D mais on laisse 21_B car ce-dernier est inférieur.
De D à F, on a 12, auquel s'ajoute 17, on inscrit donc 29_D car c'est inférieur à 32_C.
De D à G, on a 31, auquel s'ajoute 17, on inscrit donc 48_D.

B	A	C	D	E	F	G
0	\infty	\infty	\infty	\infty	\infty	\infty	B
	\textcolor{Red}{4_B}	7_B	18_B	\infty	\infty	\infty	A
		\textcolor{Red}{7_B}	18_B	21_B	\infty	\infty	C
			\textcolor{Red}{17_C}	21_B	32_C	\infty	D
				21_B	29_D	48_D

Etape 5

Cinquième étape

On choisit comme nouveau sommet celui atteint avec un poids minimal, c'est-à-dire ici E et on remplit une nouvelle ligne.

F et G sont adjacents à E :

De E à F, on a 10, auquel s'ajoute 21, on devrait donc inscrire 31_E mais on laisse 29_D car ce dernier est inférieur.
De E à G, on a 17, auquel s'ajoute 21, on inscrit donc 38_E étant donné que c'est inférieur à 48_D.

Les autres sommets sont déjà grisés.

B	A	C	D	E	F	G
0	\infty	\infty	\infty	\infty	\infty	\infty	B
	\textcolor{Red}{4_B}	7_B	18_B	\infty	\infty	\infty	A
		\textcolor{Red}{7_B}	18_B	21_B	\infty	\infty	C
			\textcolor{Red}{17_C}	21_B	32_C	\infty	D
				\textcolor{Red}{21_B}	29_D	48_D	E
					29_D	38_E

Etape 6

Sixième étape

On choisit comme nouveau sommet celui atteint avec un poids minimal, c'est-à-dire ici F et on remplit une nouvelle ligne.

G est adjacent à F :

De F à G, on a 7, auquel s'ajoute 29, on inscrit donc 36_F étant donné que c'est inférieur à 38_E.

Les autres sommets sont déjà grisés.

B	A	C	D	E	F	G
0	\infty	\infty	\infty	\infty	\infty	\infty	B
	\textcolor{Red}{4_B}	7_B	18_B	\infty	\infty	\infty	A
		\textcolor{Red}{7_B}	18_B	21_B	\infty	\infty	C
			\textcolor{Red}{17_C}	21_B	32_C	\infty	D
				\textcolor{Red}{21_B}	29_D	48_D	E
					\textcolor{Red}{29_D}	38_E	F
						36_F	G

Pour obtenir l'itinéraire le plus court, on effectue le trajet à l'envers en partant de la dernière ligne du tableau :

36_F indique qu'on vient du point F
on va chercher sur la colonne F la dernière case (29_D) qui nous indique que l'on vient du point D
on va chercher sur la colonne D la dernière case (17_C) qui nous indique que l'on vient du point C
on va chercher sur la colonne C la dernière case (7_B) qui nous indique que l'on vient du point B, qui est notre point de départ

L'itinéraire le plus court est B-C-D-F-G, il dure 36 minutes.

Un usager souhaite se rendre le plus rapidement possible de B à F.

Quel itinéraire cet automobiliste doit-il emprunter ?

F-C-D-E-G-A

B-G-E-D-C-F

F-C-D-E-G-B

B-C-A-D-G-F

On utilise l'algorithme de Dijkstra afin de rechercher la plus courte chaîne du graphe pondéré des temps de parcours.

B	A	C	D	E	G	F
0	\infty	\infty	\infty	\infty	\infty	\infty

Une fois un sommet traité, on grise verticalement le reste de la colonne.

On garde la dernière colonne afin de noter le sommet fixé à chaque étape.

Etape 1

Première étape

On part de B. Les sommets A, C, E et G sont adjacents à B. On écrit les poids correspondants avec, en indice, le sommet d'origine. Les autres sommets ont un poids infini.

B	A	C	D	E	F	G
0	\infty	\infty	\infty	\infty	\infty	\infty	B
	2_B	7_B	\infty	4_B	\infty	1_B

Etape 2

Deuxième étape

On choisit comme nouveau sommet celui atteint avec un poids minimal, c'est-à-dire ici G et on remplit une nouvelle ligne.

B est adjacent à G mais sa colonne est déjà grisée.

C, D et E sont adjacents à G :

De G à C, on a 6, auquel s'ajoute 1, on inscrit donc 7_B ou 7_C, les deux étant égaux.
De G à D, on a 5, auquel s'ajoute 1, on inscrit donc 6_G.
De G à E, on a 1, auquel s'ajoute 1, on inscrit donc 2_G car ce dernier est inférieur à 4_B.

G n'est pas adjacent à A, on réécrit donc 2_B.

Le sommet F n'est pas adjacent à A, on réécrit donc \infty.

B	A	C	D	E	F	G
0	\infty	\infty	\infty	\infty	\infty	\infty	B
	2_B	7_B	\infty	4_B	\infty	\textcolor{Red}{1_B}	G
	2_B	7_B	6_G	2_G	\infty

Etape 3

Troisième étape

On choisit comme nouveau sommet celui atteint avec un poids minimal, c'est-à-dire ici A ou E et on remplit une nouvelle ligne. On choisit A de manière arbitraire.

B est adjacent à A mais sa colonne est déjà grisée.

E est adjacent à A :

De A à E, on a 3, auquel s'ajoute 2, on devrait donc inscrire 5_A mais on laisse 2_G car ce dernier est inférieur.

A n'est pas adjacent à C et D, on réécrit donc respectivement 7_B et 6_G.

Le sommet F n'est pas adjacent à A, on réécrit donc \infty.

B	A	C	D	E	F	G
0	\infty	\infty	\infty	\infty	\infty	\infty	B
	2_B	7_B	\infty	4_B	\infty	\textcolor{Red}{1_B}	G
	\textcolor{Red}{2_B}	7_B	6_G	2_G	\infty		A
		7_B	6_G	2_G	\infty

Etape 4

Quatrième étape

On choisit comme nouveau sommet celui atteint avec un poids minimal, c'est-à-dire ici E et on remplit une nouvelle ligne.

E est adjacent à A, B et à G mais leur colonne est déjà grisée.

D sont adjacents à E :

De E à D, on a 2, auquel s'ajoute 2, on inscrit donc 4_E car c'est inférieur à 6_G.

Le sommet F n'est pas adjacent à A, on réécrit donc \infty.

Le sommet C n'est pas adjacent à A, on réécrit donc 7_B.

B	A	C	D	E	F	G
0	\infty	\infty	\infty	\infty	\infty	\infty	B
	2_B	7_B	\infty	4_B	\infty	\textcolor{Red}{1_B}	G
	\textcolor{Red}{2_B}	7_B	6_G	2_G	\infty		A
		7_B	6_G	\textcolor{Red}{2_G}	\infty		E
		7_B	4_E		\infty

Etape 5

Cinquième étape

On choisit comme nouveau sommet celui atteint avec un poids minimal, c'est-à-dire ici D et on remplit une nouvelle ligne.

C et F sont adjacents à D :

De D à C, on a 1, auquel s'ajoute 4, on inscrit donc 5_D étant donné que c'est inférieur à 7_B.
De D à F, on a 7, auquel s'ajoute 4, on inscrit donc 11_D.

Les autres sommets sont déjà grisés.

B	A	C	D	E	F	G
0	\infty	\infty	\infty	\infty	\infty	\infty	B
	2_B	7_B	\infty	4_B	\infty	\textcolor{Red}{1_B}	G
	\textcolor{Red}{2_B}	7_B	6_G	2_G	\infty		A
		7_B	6_G	\textcolor{Red}{2_G}	\infty		E
		7_B	\textcolor{Red}{4_E}		\infty		D
		5_D			11_D

Etape 6

Sixième étape

On choisit comme nouveau sommet celui atteint avec un poids minimal, c'est-à-dire ici C et on remplit une nouvelle ligne.

F est adjacent à C :

De C à F, on a 3, auquel s'ajoute 5, on inscrit donc 8_C étant donné que c'est inférieur à 11_D.

Les autres sommets sont déjà grisés.

B	A	C	D	E	F	G
0	\infty	\infty	\infty	\infty	\infty	\infty	B
	2_B	7_B	\infty	4_B	\infty	\textcolor{Red}{1_B}	G
	\textcolor{Red}{2_B}	7_B	6_G	2_G	\infty		A
		7_B	6_G	\textcolor{Red}{2_G}	\infty		E
		7_B	\textcolor{Red}{4_E}		\infty		D
		\textcolor{Red}{5_D}			11_D		C
					\textcolor{Red}{8_C}		F

Pour obtenir l'itinéraire le plus court, on effectue le trajet à l'envers en partant de la dernière ligne du tableau :

8_C indique qu'on vient du point C
on va chercher sur la colonne C la dernière case (5_D) qui nous indique que l'on vient du point D
on va chercher sur la colonne D la dernière case (4_E) qui nous indique que l'on vient du point E
on va chercher sur la colonne E la dernière case (2_G) qui nous indique que l'on vient du point G
on va chercher sur la colonne G la dernière case (1_B) qui nous indique que l'on vient du point B, qui est notre point de départ

L'itinéraire le plus court est B-G-E-D-C-F, il dure 8 minutes.

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 C à A.

Quel itinéraire cet automobiliste doit-il emprunter ?

A− B − F − D − C

F − D − C − B − E

C − D − F − B − A

C − E − F − D − A

On utilise l'algorithme de Dijkstra afin de rechercher la plus courte chaîne du graphe pondéré des temps de parcours.

On consigne les étapes dans un tableau. L'ordre des sommets dans le tableau n'a pas d'importance. On affecte le sommet de départ C d'un poids égal à 0, les autres étant affectés d'un poids infini :

C	B	D	F	E	A
0	\infty	\infty	\infty	\infty	\infty

Une fois un sommet traité, on grise verticalement le reste de la colonne.

On garde la dernière colonne afin de noter le sommet fixé à chaque étape.

Etape 1

Première étape

On part de C. Les sommets B, D et F sont adjacents à C. On écrit les poids correspondants avec, en indice, le sommet d'origine. Les autres sommets ont un poids infini.

C	B	D	F	E	A
0	\infty	\infty	\infty	\infty	\infty	C
	11_C	2_C	6_C	\infty	\infty

Etape 2

Deuxième étape

On choisit comme nouveau sommet celui atteint avec un poids minimal, c'est-à-dire ici D et on remplit une nouvelle ligne.

C est adjacent à D mais sa colonne est déjà grisée.

F, E et A sont adjacents à D :

De D à F, on a 3, auquel s'ajoute 2, on inscrit donc 5_D.
De D à E, on a 6, auquel s'ajoute 2, on inscrit donc 8_D.
De D à A, on a 9, auquel s'ajoute 2, on inscrit donc 11_D.

B n'est pas adjacent à D, on réécrit donc 11_C.

C	B	D	F	E	A
0	\infty	\infty	\infty	\infty	\infty	C
	11_C	\textcolor{Red}{2_C}	6_C	\infty	\infty	D
	11_C		5_D	8_D	11_D

Etape 3

Troisième étape

On choisit comme nouveau sommet celui atteint avec un poids minimal, c'est-à-dire ici F et on remplit une nouvelle ligne.

C et D sont adjacents à F mais leur colonne est déjà grisée.

A et B sont adjacents à F :

De F à B, on a 3, auquel s'ajoute 5, on inscrit donc 8_F.
De F à A, on a 6, auquel s'ajoute 5, on inscrit donc 11_F.

Le sommet E n'est pas adjacent à F, on réécrit donc 8_D.

C	B	D	F	E	A
0	\infty	\infty	\infty	\infty	\infty	C
	11_C	\textcolor{Red}{2_C}	6_C	\infty	\infty	D
	11_C		\textcolor{Red}{5_D}	8_D	11_D	F
	8_F			8_D	11_F

Etape 4

Quatrième étape

On choisit comme nouveau sommet celui atteint avec un poids minimal, c'est-à-dire ici B et on remplit une nouvelle ligne.

B est adjacent à F et à C mais leur colonne est déjà grisée.

B est adjacent à A :

De B à A, on a 2, auquel s'ajoute 8, on inscrit donc 10_B à la place de 11_F car 10_B est inférieur.

Le sommet E n'est pas adjacent à B, on réécrit donc 8_D.

C	B	D	F	E	A
0	\infty	\infty	\infty	\infty	\infty	C
	11_C	\textcolor{Red}{2_C}	6_C	\infty	\infty	D
	11_C		\textcolor{Red}{5_D}	8_D	11_D	F
	\textcolor{Red}{8_F}			8_D	11_F	B
				8_D	10_B

Etape 5

Cinquième étape

On choisit comme nouveau sommet celui atteint avec un poids minimal, c'est-à-dire ici E et on remplit une nouvelle ligne.

E est adjacent à A :

De E à A, on a 5, auquel s'ajoute 8, on devrait donc inscrire 13_E mais on laisse 10_B car il est inférieur.

Les autres sommets sont déjà grisés.

C	B	D	F	E	A
0	\infty	\infty	\infty	\infty	\infty	C
	11_C	\textcolor{Red}{2_C}	6_C	\infty	\infty	D
	11_C		\textcolor{Red}{5_D}	8_D	\infty	F
	\textcolor{Red}{8_F}			8_D	11_F	B
				\textcolor{Red}{8_D}	10_B	E
					\textcolor{Red}{10_B}	A

Pour obtenir l'itinéraire le plus court, on effectue le trajet à l'envers en partant de la dernière ligne du tableau :

10_B indique qu'on vient du point B
on va chercher sur la colonne B la dernière case (8_F) qui nous indique que l'on vient du point F
on va chercher sur la colonne F la dernière case (5_D) qui nous indique que l'on vient du point D
on va chercher sur la colonne D la dernière case (2_C) qui nous indique que l'on vient du point C, qui est notre point de départ

L'itinéraire le plus court est donc C - D - F - B - A, il dure 10 minutes.