Lignes 1 et 2 : Le tableau comporte deux colonnes supplémentaires pour faciliter la mise en œuvre de l’algorithme. La colonne Sél recense le sommet de plus petit coefficient de la ligne et la colonne Coef contient le coefficient affecté à ce sommet

Ligne 3 :

·          X=C.

·          Toutes les cases vides de la colonne C sont rayées.

·          Les sommets adjacents à C sont A D C.

·          Pour A : p = 0 + 4 = 4 , on écrit 4 C dans la colonne A.

·          Pour D : p = 0 + 10 = 10, on écrit  10 C dans la colonne D.

·          Pour E : p = 0 + 16 = 16, on écrit  16 C dans la colonne E.

·          On recopie les valeurs de la ligne précédente dans les cases vides.

·          Le plus petit coefficient de la ligne est 4, on sélectionne donc le sommet A (colonne Sél) et on recopie son coefficient 4 dans la dernière colonne.

Ligne 4 :

·          X=A.

·          Toutes les cases vides de la colonne A sont rayées.

·          Les sommets adjacents à A sont B D F.

·          Pour B : p = 4 + 10 = 14 , on écrit 14 A dans la colonne B.

·          Pour D : p = 4 + 4 = 8. On écrit  8 A dans la colonne D puisque 8 est inférieur au coefficient 10 précédent.

·          Pour F : p = 4 + 10 = 14, on écrit  14 A dans la colonne F.

·          On recopie les valeurs de la ligne précédente dans les cases vides.

·          Le plus petit coefficient de la ligne est 8, on sélectionne donc le sommet D (colonne Sél) et on recopie son coefficient 8 dans la dernière colonne.

Ligne 5 :

·          X=D.

·          Toutes les cases vides de la colonne D sont rayées.

·          Les sommets adjacents à D sont  F G.

·          Pour F : p = 8 + 12 = 20. Cette valeur est supérieure à la valeur précédente 14 donc on recopie la valeur précédente.

·          Pour G : p = 8 + 21 = 29. on écrit  29 D dans la colonne G.

·          On recopie les valeurs de la ligne précédente dans les cases vides.

·          Le plus petit coefficient de la ligne est 14, on sélectionne donc le sommet B (colonne Sél) et on recopie son coefficient 14 dans la dernière colonne. On aurait également pu choisir le sommet F.

ETC.

Le parcours final s’obtient de la manière suivante : La dernière ligne du tableau ne contient que « 30 J » en colonne I. Donc pour arriver en I il faut venir de J. Pour arriver en J il faut venir de H (dernière case de la colonne J) et pour arriver en H il faut venir de F etc. Le parcours 50 (à « l’envers ») est donc le suivant : I - J -  H - F - A - C soit finalement : C – A – F – H – J – I