問題タブ [shortest]

負の重みと正の重みを持つ有向グラフで以下の SPFA アルゴリズムを使用すると、どのように負のサイクルを検出できますか?

手順 Shortest-Path-Faster-Algorithm(G, s)

私はグラフストリームライブラリを使用してJavaで再帰的にグラフを構築しています..しかし、このグラフは非常に大きいため、再帰は非常に深く、スタックオーバーフローで終了します。私を信じてください、繰り返しでも私の問題は解決しません..私は途中で実行時エラーが発生します。

私の目標は、最終的に Disjktra や A* などの検索アルゴリズムを使用することです。

グラフ全体を持っていないので、部分マップの最短経路アルゴリズムなどを文献で探しています。ヒューリスティックの使用はあまり見つかりませんでした。

誰かが私にいくつかのヒントを与えることができれば幸いです (論文、アイデア; 実装は大当たりでしょう!!!! :-D) 私は PHA* などのアルゴリズムを見てきました..

上記の負の重みを持つ無向グラフにダイクストラのアルゴリズムを適用できる人はいますか? アルゴリズムが失敗したとしても。

隣接リスト:

Knight-Distance from the Chess Programming Wikiで説明されている絶対的なランクファイル距離を実装しようとしていますintが、何と何aをすべきかについて少し混乱してbいます

これを理解するために 2 組の座標 (出発地と目的地) が必要ではありませんか? 開始位置として 0,0 を使用している可能性があると思いましたが、開始位置と終了位置の違いを与えるだけで、出力が悪くなります。

これはどのように機能するのでしょうか?また、このアルゴリズムはどのサイズのグリッドでも機能しますか?それとも 8×8 だけですか?

私の問題は次のとおりです。

「バックアップ」ノードとその他のノードがあります。これらのノードから、バックアップ ノードへの共通パスを生成する必要があります。これは最小 (重み付けされていない無向グラフ) であり、毎回ソリューションは必要ありません。このパスを生成できるかどうかを知る方法。

グラフをいくつかのサブグラフに分割し、最小限の「サブパス」を検索することを考えていました。

しかし、私はグラフ理論があまり得意ではありません。Python と C++ を使用しています。

よろしくお願いします。

（申し訳ありませんが、このような質問が既にある場合は、検索しましたが見つかりませんでした）

そのため、隣接リストを使用して有向グラフの最短パスにダイクストラ アルゴリズムを実装しようとしましたが、理由がわからないため、結果が出力されません (最小距離がすべてのノードに 0 として出力されます)。 .

私が書いたコードは次のとおりです。

入力データは次のとおりです。

これは、5 つのノード、7 つのアーク (有向エッジ) があり、アークがノード 1 から 2 までコスト 10 で存在し、ノード 1 から 3 までコスト 2 などで存在することを意味します。

ただし、出力は間違っています。プログラムがどこで失敗するかわかりません。ここから主なアイデアを取りました: http://community.topcoder.com/tc?module=Static&d1=tutorials&d2=standardTemplateLibrary2#dijkstra1 (最後に、priority_queue を使用したダイクストラのアルゴリズムのアイデアを提供します)。

前もって感謝します。

ラウル