問題タブ [floyd-warshall]

Floyd-Warshall アルゴリズムを理解するのに苦労しています。手で行う方法を知っているのと同じように、それがどのように機能するかは知っていますが、コンピューターの知覚を通じて理解する必要があります。

k、iおよびjは反復用の変数であり、値まで反復しnます。これはネストされたループであり、各ノードを調べてから最短パスを見つけますか?

迷路に Floyd–Warshall アルゴリズムを実装して、迷路内のある点から他のすべての点までの距離を計算しようとしています。何らかの理由でk、列と行の間の最大値に等しい a を使用すると、間違った答えが得られます。

k特定の迷路のすべての長さに対して正しい値でこれを解決する方法はありますか?

つまり、n×n 以外の行列に Floyd-Warshall アルゴリズムを使用する方法はありますか? つまり、am×n 行列の場合、m!= n?

ノードが実数 (正と負) に重み付けされている無向グラフを通る最短経路を見つける必要があります。これらの重みは、ノードに入ることによって獲得または解放できるリソースのようなものです。

パスの総コスト (リソースの合計) はそれほど重要ではありませんが、0 より大きくなければならず、長さは可能な限り短くする必要があります。

たとえば、次のようなグラフを考えてみましょう。

最短パスは AEFED です

ダイクストラのアルゴリズムだけではうまくいきません。負の値を処理できないからです。そこで、いくつかの解決策を考えました。

最初のものは、ダイクストラのアルゴリズムを使用して、重みを考慮せずに、各ノードから出口ノードまでの最短経路の長さを計算します。これは、A* のようなある種のヒューリスティック値のように使用できます。このソリューションが機能するかどうかはわかりません。また、非常にコストがかかります。Floyd-Warshall のアルゴリズムを実装することも考えましたが、どうすればよいかわかりません。

別の解決策は、重みを考慮せずにダイクストラのアルゴリズムを使用して最短パスを計算することでした。パスのリソースの合計を計算した後、ゼロ未満の場合は、各ノードを調べて、リソースの合計をすばやく増やすことができる隣接ノードを見つけ、それをに追加します。パス (必要に応じて数回)。このソリューションは、リソースの合計を増やすのに十分な可能性があるノードがある場合には機能しませんが、計算された最短パスから遠く離れています。

例えば：

この問題を解決するのを手伝ってくれませんか?

編集:最短経路を計算するときに、リソースの合計がゼロに等しいポイントに到達した場合、その経路は有効ではありません。ガソリンがなくなると先に進むことができないためです。

Floyd-Warshall-Algorithm を実装して、全ペア最短経路問題を解決しました。これで、簡単な変更でミニマックスまたはマキシミン パスも計算できることがわかりました。しかし、結果の意味がわかりません (ミニマックス パスとは)。ウェブでいくつかの説明を見つけましたが、混乱しています。

ミニマックス - グラフ問題のミニマックスには、パスに沿って最大コストを最小化する 2 つのノード間のパスを見つけることが含まれます。

Maximin - Minimax とは逆に、パスに沿って最小コストを最大化するパスを見つける必要があるという問題があります。

誰か他の説明や例を教えてください。

私はこれにドリルダウンする問題に取り組んでいます:

接続された無向グラフがあります。ノードに複数回アクセスせずに、すべてのノードにアクセスする必要があります。任意のノードで開始および終了できます。

これについてどうすればよいですか？可能なすべての開始ノードに同様のアルゴリズムを適用するFloyd-Warshall必要がありますか、それともより良い方法がありますか?

ありがとう。

私は現在、Java で小さなタワーディフェンス プロジェクトに取り組んでおり、経路探索に行き詰まりました。私は A* dijkstra などについて多くのことを読みましたが、経路探索には Floyd-Warshall を使用するのがおそらく最善であると判断しました (少なくとも、すべてのペアの最短経路問題を解決しているように思えます)。

とにかく、私は自分でそれを実装しようとしましたが、本来のように機能しません。ウィキペディアのコードを最初に使用しましたhttp://en.wikipedia.org/wiki/Floyd%E2%80%93Warshall_algorithm

だからここに私のコードがあります：

}

Floyd-Warshall アルゴリズムはグラフで機能するように設計されているため、すべてのノードがその隣接ノード (接続先のノード) を認識しているグラフを作成します。

私は実際にそれがどこでうまくいかないのか今はわかりませんが、どういうわけかそうです。しかし、少なくとも隣接行列の初期化は機能しているようです。

floydwarshall 関数では、next[][] で次のノードのインデックスを取得したかったのですが、null または 10/11 しか取得できませんでした。

だから私の質問は、私が間違っていること、または私のアプローチがまったく間違っていることです? 誰かが私を助けてくれることを願っています。さらに情報が必要な場合はお尋ねください

pS 下手な英語でごめんなさい ;)

5x5行列のすべてのペアの最短経路行列を見つけようとしていますが、出力に正しい答えが表示されていません。

これが初期マトリックスと私の出力です：

ただし、実際の解決策は次のとおりです。

ご覧のとおり、初期マトリックスは正しく読み取られますが、コードのどこかで、数学が正しく適用されていないか、何かが混乱しています。

以下は私のコードです、あなたは私の間違いを見つけることができますか？

重み付けされていない有向アシル グラフが与えられた場合、Floyd-Warshall アルゴリズムを適応させて、2 つの頂点間のパスの数をカウントしようとしています。私のコードは現在次のようになっています。

1 から n のすべての k に対して 1 から n のすべての i に対して 1 から n のすべての j に対して Aij = Aij + (Aik * Akij)。

したがって、最小距離を確認して置き換える代わりに、次のことを行っています。

i( , j)間のパスのk数 + ( からのパスのカウント * からのパスiのカウント)kkj

私の最終的な配列には、任意の 2 つの頂点間のパスの数が必要です。

これが 2 つの頂点間の単純なパスの数を与えないことを証明することはできませんが、このアプローチを他の場所で使用する提案はありません。

誰かがこれが失敗する反例を提供できますか?

PS: これは私の宿題ではなく、私が取ったプログラミングの演習です。

以下で説明するように、グリッド構造の最短経路を見つけるために、フロイドのアルゴリズムを実装する方法を数日間理解しようとしています。このようなものをどのように実装するかについて、誰かが私を正しい方向に向けることができますか? ありがとう。

入力：

• 開始/終了座標
• ユーザー入力は 0 から 10 の間である必要があります。
• 障害物の数
• 左上と右下の障害物座標

出力：

• 通過するすべての座標を示すパス
• int としての距離

制限：

• 障害物を重ねることはできません
• Start と End は、長方形の障害物内には設定できません
• パスには、長方形のエッジに沿った移動を含めることができますが、それらを通過することはできません
• パスは、斜めではなく、水平および垂直にのみ進むことができます
• 隣接する 2 つの頂点間の距離は 1

121x121 配列の条件を生成するのに助けが必要です。

これは私がこれまでに持っているものです。

Two simple questions and my brain's not working. I'm using Floyd's Algorithm and trying to reconstruct the path taken from vertex U to vertex V. Here's my code to reconstruct the path.

For one example, let u = 0 and v = 3, and let the shortest path from 0 to 3 be 0,1,2,3. However I have two problems. My pathList is an instance variable of the class and:

1. I want the list to return "0,1,2,3" but it only returns "0,1,2", or if i replace pathList.add(u) with pathList.add(v), then it returns only "1,2,3" I could not figure out how to make it return the entire path including both end vertices. trying to put pathList.add(other vertex) will cause it to duplicate every intermediate vertex.
2. When I call the method again, letting u = 3 and v = 0, and let the shortest path from 3 to 0 be "3,0" (already the shortest path), it just adds onto my previous list making it with my error from above "0,1,2,3" or "1,2,3,0" when it's supposed to be just "3,0"

Any help?