重み付きグラフで最適なアルゴリズム問題について質問があります。私はウェイト、セーブポイントを持つリスト、開始ノードと終了ノード、そしてステップの最大距離を持つedgelistを与えられます。 出力は、開始ノードと終了ノードから1ステップでアクセス可能なセーブポイントのリストでなければなりません。最短経路アルゴリズム
私はセーブポイントのリストの各点から、ダイクストラのアルゴリズムのいくつかの種類を考えました。
私は多くのセーブポイントを持っている場合、私はパスの多くを複数回計算するので、私は、それは良いアイデアだかはわかりません。すべてのアイデアや助けを歓迎します！
ありがとうございます！
あなたは体重がそうでなければ、問題は非常に難治性となり、負にすることはできませんという条件を持っている必要があります。それ以外の場合は、訪問先のノードごとに距離をマークした、幅広い最初の検索です。だから、以前の動きが低コストで早く訪問したということは、ノードを再訪しないということです。
あなたはすべてのアクティブノードのプライオリティキューを維持するので、あなたは、最低コストのノードを毎回チェックしています。優先キューは、実際には最も難しい部分です。私のバイナリイメージライブラリhttps://github.com/MalcolmMcLean/binaryimagelibraryのA *アルゴリズムをチェックすると、そのための優先待ち行列を取ることができます。迷路上のA *は、グラフ上の最短経路と非常によく似ていますが、正確な最短経路を持たなければならないのでヒューリスティックはありません。タイルあたり4/8のエッジではなく、任意の数の接続。
ありがとう、私はパラレルを見ることができます！申し訳ありませんが、私はそれを言いませんでしたが、重量はすべてpostiveです、それはずっと簡単です。 – Timmathstf
開始ノードと終了ノードの両方からdijkstraを実行します。グラフをトラバースすると、ステップサイズよりも大きな総コストを持つノードに到達するまで表示されるセーブポイントが追跡されます。 –
ああ、それははるかに良い音！どうもありがとうございました！ – Timmathstf