Mon exposé
Comment trouver le chemin le plus court entre deux villes ?
Tout d'abord, il faut comprendre ce qu'est un graphe.C'est un modèle abstrait représentant un réseau, ensemble de rond(Nœud) et ensemble de trait qu’on appelle lien. Dans notre cas nous utilisons un graphe à poids. Par exemple sur google map les nœuds sont des intersections et les liens sont des routes et le nombre qui est associé au liens est le temps de trajet.
Il y a donc deux problèmes à résoudre. Le premier étant
comment trouvé tous les chemins.
Pour répondre à la question il y a deux algorythme :
L'Algorithme de parcours en profondeur et L’Algorythme de parcours en largeur.Interressons nous a l’Algorythme de parcours en porfondeur qui possède la même utilité que le DFS mais peut en plus calculer la distance
entre les différents points qu'il parcourt avant d'avoir tout exploré. C'est un algorithme de recherche qui progresse à partir d'un sommet S en s'appelant récursivement pour chaque sommet voisin de S. pour chaque sommet, il marque le sommet actuel, et il prend
le premier sommet voisin jusqu'à ce qu'un sommet n'ait plus de voisins (ou que tous ses voisins soient marqués), et revient alors au sommet père. Il peut en plus calculer la distance enre deux nœud
explorer(graphe G, sommet s)
marquer le sommet s
afficher(s)
pour tout sommet t fils du sommet s
si t n'est pas marqué alors
explorer(G, t);
.
Une fois que l’on connait les chemins c’est l’algorithme de Dijkstra qui permet de résourdre le problème.Il permet, par exemple, de déterminer un plus court chemin pour se rendre d'une ville à une autre connaissant le réseau routier d'une région.
Les arêtes sont munies de poids, et deux sommets de ce graphe, trouver un chemin entre les deux sommets dans le graphe, de poids minimum.
.
Sous python : .
Si nous voulons prendre en compte le trafic il faudrait avoir accés au temps mis entre deux noms et non la distance.