フィボナッチ ヒープを使わずに Dijkstra と Sedgewick-Vitter アルゴリズムを実現する必要があります。ダイクストラ フル インターネットに関する情報ですが、疑似コードや Sedgewick-Vitter アルゴリズムの例は見つかりませんでした。McHugh の Algorithmic Graph Theory book にいくつかの情報があることがわかりましたが、無料の pdf は見つかりませんでした。では、このアルゴリズムを知っていて、情報、疑似コード、リンクを共有できる人はいるでしょうか?
乾杯！
ユークリッド距離のグラフを考えてみましょう。ソースはsで、宛先はtです。
ご存知のように、ダイクストラのアルゴリズムは、距離（s、x ）が減少しない順に頂点xにアクセスします。
A *アルゴリズムは、距離（s、x）+ h（x ）が減少しない順序で頂点xにアクセスします。関数hは、許容可能なヒューリスティックである必要があります。これは、この設定では、h（x）≤distance（x、t）を意味します。hのさまざまな選択を検討してください。
h（x）=0。これにより、A*はダイクストラのように動作します。
h（x）=距離（x、t）。これは、可能な限り最高の許容可能なヒューリスティックです。A *は、distance（s、x）+ distance（x、t）= distance（s、t ）の頂点、つまりsからtまでの最短経路上の頂点のみを訪問します。残念ながら、このhの選択は計算にコストがかかります。
h（x）= || x -- t ||。直線距離は時間O（1）で計算可能であり、常に距離の下限です。
最後のヒューリスティックは、 sからtまでかなりまっすぐなショットがある場合にうまく機能しますが、迂回路が積み重なると、A*は「邪魔にならない」多くの頂点を訪問します。
Sedgewick–Vitterは、h（x）= a ||を使用して11まで上げます。x --t || _ > 1の場合、このヒューリスティックは許容されないため、最短経路が見つからない可能性がありますが、早期の迂回を罰することにより、ソリューションの品質をあまり低下させずに検索スペースをトリミングできることを願っています。