Bonjour

J'ai un problème classique qui consiste à parcourir une matrice afin de trouver le chemin le plus court entre deux sommets (villes). J'arrive à concevoir le parcours à la main, mais j'ai du mal à trouver un algorithme pour l'automatiser.

Ainsi au départ nous avons une matrice telle que:
Chaque ligne représente une ville et les colonne associées représentent les villes desservies depuis la ville avec les distances correspondantes.
_______ ________________________________
______|_____0___|___1___|___2____|___3_|
0 paris | 1 : 170m | 2 : 140| 3 : 453 |-1 : 0 |
1 nice | 0 : 132m | 2 : 274| 3 : 143 |-1 : 0 |
2 lyon | 1 : 170m | 3 : 130| 0 : 875 |-1 : 0 |
3 metz | 0 : 170m | 2 : 140| 1 : 324 |-1 : 0 |

On peut coder cette matrice ainsi:

Code : Sélectionner tout - Visualiser dans une fenêtre à part
1
2
3
4
5
6
7
8
9
10
 
typedef struct nom
{
int destinations;
int distance;
} chemin_t;
 
chemin_t Chemin[nb_ville][nb_chemin];
 
//nb_ville et nb_chemin sont des constantes definie avec les valeurs 4 et 4

Le problème:

choisir une ville de départ et une ville d'arrivée, [représentées par leur valeur numérique] et parcourir la matrice en profondeur pour trouver le chemin le plus court liant les deux ville.

Voici donc ce que je parviens à faire manuellement, mais sans trouver d'algorithme capable de l'automatiser.

depart=0 (paris) arrivée = 3 (metz)

la ville_courante = depart

Je me sers d'un tableau parcours[nb_chemin] pour y classer les villes parcourues.

ainsi:
parcours[0] = ville_courante


on étudie la première ville disponible depuis 0(paris).
cette ville c'est 1 (nice) avec distance 170m.

On vérifie si cette ville [obtenu par chemin[depart][0].destination;] n'a pas pour valeur -1 (indiquant fin de la liste) et s'il ne se trouve pas déjà dans le tableau parcours.

Si tel n'est pas le cas on met cette valeur dans la case suivante du tableau parcours.

ce qui donne:
Parcours [0][1][-][-]

ensuite c'est 1(nice) qui devient la ville_courante. Et donc on va étudier la première ville disponible depuis 1. Cette ville est 0 (paris) 0!=-1, mais 0 existe déjà dans le tableau parcours.

Alors on avance, et on lit la deuxieme ville dispo depuis 1
cette ville c'est 2 : 2!=-1 et il n'est pas dans le tableau parcours.

alors on rajoute cette ville dans le tableau parcours qui devient

Parcours[0][1][2][-]

des lors c'est 2 qui devient ville_courante
On va alors étudier la premier chemin dispo depuis 2
chemin[2][0].destination = 1
1!=-1, mais 1 existe déja dans parcours
on incrémente la destination
chemin[2][1].destination = 3

3!=-1 et 3 n'est pas dans parcours
on l'y met. Or 3 = arrivée.

Donc premier chemin =
Parcours[0][1][2][3]

Cependant tant que chemin[ville-courante][i].destination!=-1 on continue.

Donc on étudie chemin[2][3].destination.

Ceci est égal à -1 (Fin liste).

Il faut donc décrémenter pour trouver la ville courante précédente.

cette ville était 1. Et on n'avait pas terminé de parcourir toutes les villes dispo depuis 1.

Donc le tableau parcours a cette forme:
Parcours [0][1][-][-]

..et on s'était arrêté au chemin[1][1].destination.
On continue donc l'exploration des chemins dispo depuis 1
la ville suivante sera donc: chemin[1][2].destination = 3.

youppi! c'est ce qu'on cherchait.
On a donc Parcours[0][1][3][-]

Mais comme il existe encore des destination dispo non parcourue on continue/
on étudie alors le chemin[1][3].destination. sa valeur = -1.

Il faut décrémenter et retrouver la ville_courante précedente à savoir 0.

A ce stade nous avons déjà parcouru l'ensemble des chemin menant à metz depuis Chemin[0][0].destination (cad premiere ville dispo depuis ville de départ)

On va donc réaliser les memes opération pour toutes les villes dispo depuis la ville de départ, jusqu'à ce qu'on arrive à chemin[0][i].destination = -1

Où 0 = ville de départ, et i la derniere ville dispo depuis ville de départ.

Bon, si vous avez réussi à lire ça jusqu'au bout, alors plizzz