問題タブ [floyd-warshall]

いくつかの負のエッジ重みを持つ重み付きDAGがあり、その中のすべての最短パスを見つけたいと思っています。O（n ^ 2）よりも複雑なアルゴリズムはありますか？（私のグラフは完全です。つまり、{1..n}の任意のi、jおよびi <jに対してエッジ（i、j）があります）。

ありがとう

重複の可能性:
Android ロック パスワードの組み合わせ

尊敬する先生、私は 1 から 9 までの数字を持つ 3x3 マトリックスを与えられて、可能なすべてのユニークなパターンを見つけることを求める質問に出くわしました. Androidのロック画面と同じです。探し方を教えていただけないでしょうか?? これにフロイド・ウォーシャルを使用して、後続のマトリックスで値が変化するたびにカウントを増やすことができると考えていましたか??

私が取り組んでいるゲームでパス検索を機能させるために、1週間試してきました。私はフロイド・ウォーシャルのアルゴリズムのこの実装を使用しています。問題をこのループ内に絞り込むことができたと思います。

すべてのノードが他のすべてのノードに接続し、すべての接続の重みが 1 である 4 つのノードでテストしてきました。これは、ループ前のすべての関連変数の値です。

出力：

これは予想通り

出力：

これも予想通り。

出力：

これも予想通り。

出力：

ここに問題があると思います。出力にはすべての異なるノードが含まれていると予想していましたが、ここで見つかった 2 つのノードのみが getShortestPath 関数で機能します。これはループの正しい出力であり、私が理解している限り、順序は無関係であるはずです。

ループ内で何が問題を引き起こしているのか、またはアルゴリズムについて何か誤解しているのかどうかはわかりません。

Floyd-Warshall のアルゴリズムの場合、ループの順序は k、i、および j です。ループの順番を間違えて、誤って i、k、j と書いてしまったらどうなるでしょうか? プログラムが機能しないのはどのような場合ですか? ありがとう！

割り当ての場合、O（n 4）時間を使用して有向グラフの推移閉包を計算するアルゴリズムを見つけるように求められます。フロイドウォーシャルアルゴリズムについてはすでに学びましたが、これははるかに優れているので、誰かがO（n4）時間で実行されるアルゴリズムを作成するのを手伝ってもらえますか？そのようなアルゴリズムはありますか？

私はそれが質問のばかげているように見えることを知っています。なぜ私たちがそれを行うのに遅い方法を見つけるように求められているのか、私は本当に理解していません。

フロイドのアルゴリズムを使用して、98 個のウェイポイント (各迷路の頂点にある) を持つ迷路を通る最速ルート マトリックスを生成しようとしています。アルゴリズムが実行されると、Distance マトリックス (2 つのノード間の最適な距離) と Path マトリックス (任意の 2 つのノード間の最適なパスに移動する次のノード) の 2 つのマトリックスが生成されます。

距離行列は、前のコードで生成した隣接行列で初期化されます。また、ウェイポイントごとに 4 つの可能な近隣ウェイポイントのそれぞれへのポインターを含むデータ構造も生成しますが、パス マトリックスの生成にはこのデータ構造を使用しませんでした。

ここに私のC＃コードがあります：

このコードによって生成されたパス マトリックスを使用するボットは、ほとんどの状況で (パス マトリックスが壁を通過するように指示しているため) 失敗するため、パス マトリックスを正しく計算していないと思います。

私は何時間もこのコードを見つめてきましたが、何が間違っていたのか頭に浮かびません。迷路ナビゲーション コードで使用する正しいパス マトリックスを生成するにはどうすればよいですか?

このスニペットが2つの頂点間の最短距離を見つける理由について簡単な説明はありますか?

そして、これはしません

( k は 2 番目のスニペットの最も内側のものです)

Floyd Warshall アルゴリズムについて読んで検索しましたが、理解できたと思います。しかし、本「アルゴリズムの紹介（トーマス・H・コーメンの本）」で読んだ例では、ある時点で積み重ねました。私は混乱しました。これは本と同じ図です。私の質問は最後のステップ、つまり π(5) にあります。例を次に示します: http://integrator-crimea.com/images/fig653_01_0.jpg

上記の私の混乱を解決できる人はいますか？それは本に間違って書かれていますか？

C++ で Floryd アルゴリズムを実装しようとしています。

私はすでにこれを持っています：

a は、エッジが開始するノードを意味します。

b はエッジが終了するノードを意味します。

t はエッジの時間を意味します。

m はエッジの数を意味します。

n はノード数を意味します。

コードを試すと、プログラムがクラッシュして、「式: ベクトル添え字が範囲外です」と表示されます。

私はこれを解決できなかったので、皆さんが私を助けてくれることを願っています!

Floyd-Warshallアルゴリズムを実装しています。

約50ノードの完全グラフがあります。すべてのノード間の最大パスを見つけたいと思います。アルゴリズムが返すパスは、任意の長さ1 <x <50にすることができます。この長さは、最大で3〜4エッジの長さである必要があります。これを行うために、アルゴリズムを変更するにはどうすればよいですか？