最短パスを解決するためのバックトラッキングアルゴリズム？

Question

私は昨夜までネット全体で広範囲に検索してきましたが、バックトラッキングアルゴリズムを使用して特に最短のパスの問題を解決する方法を議論するリソースを見つけることができないようです。私はこのアルゴでそれを解決しようとしましたが、私には意味がありません。それがn-queensの問題である場合、それはこれほど複雑ではありません。

それで、誰かが私にいくつかのリソースを示すいくつかのインターネットリンクを与えることができますか？とても感謝しています。

*更新：好奇心が強い、バックトラッキングアルゴリズムは実際に最短のパスの問題を本当に解決できますか？

Answer 1

バックトラッキングAlgoritmを使用するように指定された有線です。実際、Dijkstra SPFAまたはBellman-Fordアルゴリズムは問題を解決するのに最適です。バックトラッキングを使用する必要がある場合は、悪い時間の複雑さしか到達できないことを恐れています。次の道路セグメントを試してみてください。選択したセグメントの合計長が「現在の最短パス」を超えたら、バックトラッキングを開始します。

Answer 2

バックトラッキングはそれを解くことができますが、非常に遅いです...私はあなたがDijkstra O（n^2）、Heap O（nlogn）、Bellman-Ford O（NE）またはSPFA O（KE）（ke）を備えたDijkstraが必要だと思います）私にとっては、SPFAが好きです...