Algorithme de Djikstra

L’algorithme de Djikstra est un algorithme qui permet de trouver le chemin le plus court entre deux points dans un réseau. Un réseau est un ensemble de nœuds reliés par des arcs, qui peuvent avoir des longueurs ou des coûts différents. Par exemple, un réseau routier est un réseau où les nœuds sont des villes et les arcs sont des routes, avec des distances ou des temps de parcours. L’algorithme de Djikstra consiste à partir du point de départ, et à explorer les nœuds voisins en les classant par ordre croissant de distance ou de coût. On choisit ensuite le nœud le plus proche, et on répète l’opération jusqu’à atteindre le point d’arrivée. A chaque étape, on met à jour les distances ou les coûts des nœuds non explorés, en tenant compte du chemin parcouru. L’algorithme de Djikstra garantit de trouver le chemin le plus court, si le réseau ne contient pas d’arcs négatifs (c’est-à-dire qui font diminuer la distance ou le coût).

Exemple :

Supposons que vous vouliez aller de Paris à Lyon en voiture, en passant par le réseau autoroutier. Vous pouvez utiliser l’algorithme de Djikstra pour trouver le trajet le plus rapide, en considérant que le coût d’un arc est le temps de parcours sur l’autoroute correspondante. Voici comment procéder :

• On part de Paris, qui est le nœud de départ. On note que le coût pour atteindre Paris est 0, et que les autres nœuds ont un coût infini pour l’instant.
• On explore les nœuds voisins de Paris, qui sont Orléans, Reims et Troyes. On note que le coût pour atteindre Orléans est 1h15, celui pour atteindre Reims est 1h30, et celui pour atteindre Troyes est 1h45. On choisit le nœud le plus proche, qui est Orléans.
• On explore les nœuds voisins d’Orléans, qui sont Bourges, Clermont-Ferrand et Auxerre. On note que le coût pour atteindre Bourges est 1h15 + 1h = 2h15, celui pour atteindre Clermont-Ferrand est 1h15 + 2h30 = 3h45, et celui pour atteindre Auxerre est 1h15 + 1h30 = 2h45. On met aussi à jour le coût pour atteindre Troyes, qui est 1h15 + 2h = 3h15. On choisit le nœud le plus proche, qui est Bourges.
• On explore les nœuds voisins de Bourges, qui sont Moulins, Chalon-sur-Saône et Lyon. On note que le coût pour atteindre Moulins est 2h15 + 1h = 3h15, celui pour atteindre Chalon-sur-Saône est 2h15 + 2h = 4h15, et celui pour atteindre Lyon est 2h15 + 2h30 = 4h45. On met aussi à jour le coût pour atteindre Clermont-Ferrand, qui est 2h15 + 2h = 4h15. On choisit le nœud le plus proche, qui est Moulins.
• On explore les nœuds voisins de Moulins, qui sont Roanne et Lyon. On note que le coût pour atteindre Roanne est 3h15 + 1h = 4h15, et celui pour atteindre Lyon est 3h15 + 1h30 = 4h45. On met aussi à jour le coût pour atteindre Chalon-sur-Saône, qui est 3h15 + 1h30 = 4h45. On choisit le nœud le plus proche, qui est Roanne.
• On explore le nœud voisin de Roanne, qui est Lyon. On note que le coût pour atteindre Lyon est 4h15 + 1h = 5h15. On met aussi à jour le coût pour atteindre Lyon par Bourges, qui est 4h45. On choisit le nœud le plus proche, qui est Lyon.
• On a atteint le nœud d’arrivée, qui est Lyon. On a trouvé le chemin le plus court, qui est Paris – Orléans – Bourges – Moulins – Roanne – Lyon, avec un coût de 5h15.

Retourner à l'index du lexique