Supposons que nous passions de 1 à 5. L'itinéraire le plus court sera le 1-4-3-5 (total: 60 km).
On peut utiliser l'algorithme de Dijkstra pour ce faire.
Maintenant, le problème est que l'itinéraire le plus court n'est pas toujours le plus rapide, en raison des embouteillages ou d'autres facteurs.
Par exemple:
- 1-2 est connu pour avoir des embouteillages fréquents, il doit donc être évité.
- Tout à coup, un accident de voiture se produit le long de 4-3, il faut donc également l'éviter.
- Etc...
Donc, nous pouvons probablement accélérer sur la route 1-4-5, en raison d'aucun embouteillage / accident, nous arriverons donc à 5 plus rapidement.
Eh bien, c'est l'idée générale, et je n'ai pas encore pensé à plus de détails.
Existe-t-il un algorithme pour résoudre ce problème?
Réponses:
Depuis que vous avez mis de la congestion dans l'image, faites attention à ne pas vous faire prendre par le paradoxe de Braess . Si tout le monde choisit le chemin optimal, cela se traduit par une diminution du temps de trajet pour tout le monde.
la source
Oui: Dijkstra
Dijkstra fonctionne aussi bien pour cette situation.
Vous utilisez simplement le temps plutôt que la distance comme poids de chaque arc.
la source
Oui. L'algorithme de Dijkstra résoudra ce problème.
Le problème dans votre cas est que vous supposez automatiquement que le chemin le plus court équivaut à la distance parcourue, alors qu'en fait il correspond de manière plus appropriée au COÛT de prendre un itinéraire.
Si un chemin a un barrage routier, son COÛT doit être plus élevé et l'algorithme s'applique toujours.
la source
Vous devriez simplement pouvoir remplacer votre distance par le temps entre les nœuds et la résoudre de la même manière.
la source
Dijkstra
Comme dit précédemment, il n'est pas seulement utilisé pour la distance la plus courte. Je crois que cette animation donne une bonne compréhension du "pouvoir" (faute d'un meilleur mot) de Dijkstra:
la source