Modéliser un calcul d'itinéraire comme un problème de plus court chemin dans un graphe

En 30 secondes

• Un graphe modélise un réseau routier : les lieux deviennent des sommets, les liaisons directes deviennent des arêtes pondérées (distance, temps).
• Le poids total d'un chemin est la somme des poids de toutes les arêtes qu'il emprunte ; le plus court chemin est celui dont le poids total est minimal.
• Un chemin avec moins d'arêtes n'est pas forcément le plus court : seul le poids total compte. Sur un très grand graphe, un algorithme comme Dijkstra évite d'énumérer tous les chemins.

Ce que tu sauras faire

• Modéliser un réseau routier par un graphe : représenter chaque lieu par un sommet et chaque liaison directe par une arête portant un poids (distance, temps).
• Calculer le poids total d'un chemin dans un graphe en additionnant les poids de toutes les arêtes qu'il emprunte.
• Déterminer le plus court chemin entre deux sommets d'un petit graphe en comparant le poids total de tous les chemins possibles.

Les mots à connaître

Graphe

représentation d'un réseau (routier, ferroviaire...) sous forme de sommets reliés par des arêtes, utilisée pour modéliser des liaisons entre des lieux ou des éléments.

Sommet

point du graphe qui représente un lieu (un carrefour, une ville, une adresse) dans la modélisation d'un réseau.

Arête

liaison directe entre deux sommets d'un graphe, représentant une route ou un tronçon reliant deux lieux sans passer par un troisième.

Le piège classique

Croire que le chemin avec le moins d'arêtes est automatiquement le plus court. Un chemin plus long en nombre d'arêtes peut avoir un poids total plus petit si ses arêtes sont individuellement moins lourdes.

L'astuce

Un graphe = des sommets (les lieux) reliés par des arêtes (les liaisons), chacune pondérée par sa distance ou son temps.