Algorithme pour parcourir plusieurs endroits pour trouver l'itinéraire le plus court

Question

Je crée un programme pour les touristes. Ils vont quitter l'hôtel et aller à disons 3 endroits différents (B, C, D). J'ai besoin de trouver le chemin le plus court pour traverser les emplacements B, C et D. Le point final n'est pas important, il peut être l'un ou l'autre.

Est-ce que Dijkstra's Algorithm peut le faire? J'ai besoin de mettre en œuvre l'algorithme en utilisant PHP.

Answer 1

L'algorithme de Dijkstra peut résoudre ce problème. Je ne suis pas sûr que ce soit optimal. Mais au moins, cela résout votre problème. Dans le pire des cas, vous pouvez énumérer tous les ordres avec lesquels vous atteignez chaque nœud (c'est-à-dire, BCD, BDC, CDB, CBD, DBC, DCB). Ensuite, exécutez l'algorithme de Dijkstra pour obtenir le chemin le plus court. Prenez l'ordre BCD par exemple, exécutez le Dijkstra pour obtenir le plus court de l'hôtel à B, de B à C, enfin de C à D, les résumer pour obtenir le chemin le plus court pour cette commande. La plus courte parmi toutes les commandes est la solution optimale pour votre problème.