Calculer un itinéraire : comment ça marche ?
Pour trouver le meilleur trajet entre deux points (à pied, en voiture, à vélo…), le logiciel utilise un graphe :
- Un graphe est une structure composée de nœuds (carrefours, arrêts, lieux) reliés par des arêtes (routes, chemins).
Représentation algorithmique
- Chaque arête se voit attribuer une valeur (distance, temps, coût).
- Des algorithmes, comme celui de Dijkstra, recherchent le chemin le plus court ou le plus rapide.
Exemple
Pour aller de A à D, si le graphe contient les chemins A-B, B-C, C-D et A-C directement :
- L’algorithme recherche toutes les possibilités et sélectionne celle dont la somme des distances est la plus faible.
Applications
- Calculer un trajet avec Google Maps ou OpenStreetMap
- Navigation GPS embarquée dans les voitures
Mise en pratique
Chaque fois que vous définissez un point de départ et d’arrivée dans une application, un algorithme sur graphe décide du trajet proposé.
