最短ルートを見つけるいくつかの場所をトラバースするアルゴリズム

Question

私は観光客のためのプログラムを作成しています。彼らはホテルを出て、3つの異なる場所（B、C、D）を言います。私は、B、C、Dの位置を通過する最短ルートを見つける必要があります。エンドポイントは重要ではありません。

できますDijkstra's Algorithmこれを行いますか？

PHPを使用してアルゴリズムを実装する必要があります。

Answer 1

ダイクストラのアルゴリズムはこの問題を解決できます。私はそれが最適かどうかはわかりません。しかし、少なくとも、それはあなたの問題を解決します。最悪の場合、各ノードに到達するすべての注文（つまり、BCD、BDC、CDB、CBD、DBC、DCB）を列挙することができます。その後、Dijkstraのアルゴリズムを実行して最短経路を取得します。例えば、BCDを注文し、ホテルから最短距離を得るためにDijkstraを実行し、BからCまで、最後にCからDに至るまで、これらを合計してこの注文の最短経路を得る。すべての注文の中で最短のものが問題の最適な解決策です。