問題タブ [floyd-warshall]

私はいくつかの古いコンテストの質問を調べていましたが、これは楽しそうに見えました。http://dwite.ca/old/Problem5Jan2006.pdf、フロイドウォーシャルアルゴリズムを使用して、任意のノードから任意のノードへの最短経路を取得しようとしました。他のノード、あなたたちは私が間違ったことを見ることができますか？コンテストの質問ページに記載されている目的の出力が得られません

Floyd Warshall アルゴリズムを実装しましたが、動作しますが、問題は、定義されていないすべてのパスを見つける方法がわからないことです。Web を検索しましたが、グラフに負のサイクルがあるかどうかを検出する方法しか見つかりません。

グラフでアルゴリズムを実行した後:

隣接行列を取得します。

ノード i が負のサイクルの一部である場合、行列の位置 d[i][i] に負の値があることがわかっています。したがって、マトリックスの対角線をチェックすると、負のサイクルの一部であるすべてのノードを見つけることができます。したがって、上記の例を見ると、ノード 1 と 2 が負のサイクルの一部であることがわかります。問題は、定義されているパスと定義されていないパスを見つけたいということです。負のサイクルを介して A から B に到達できる場合、パスの長さは任意に短くなる可能性があるため、未定義にする必要があります。

問題は、未定義のパスをすべて見つけるにはどうすればよいですか?

アルゴリズムが行列を返すようにしたい:(上記の代わりに)

d[i][j] = INF は i と j の間にパスがないことを意味し、 -INF は i と j の間に任意の小さなパスがあることを意味し (パスはどこかで負のループを通過します)、そうでない場合は d[i ][j] i と j の間の最短の長さ。

パスごとにテストすることを考えていましたが、おそらく遅すぎます。この問題を解決するための標準的な方法があるはずですよね?

ありがとうございました

Floyd-Warshall アルゴリズムは動的であるため、常に最適なソリューションを提供する必要があります。したがって、私を混乱させているのは、アルゴリズムの各セグメントでのこれらの最適解の性質が何であるかです。特に、次の 3 つの質問を理解しようとしています。

• 反復 0: 反復が発生する前に提供される最適な (つまり、正確な) ソリューションは ?

• 反復 1: この反復の最後に提供される最適な (つまり、正確な) ソリューションは?

• 反復 i (任意の i > 0 の場合): この反復の最後に提供される最適な (つまり、正確な) 解は?

誰でもこれらの懸念に光を当てることができますか?

Floyd-Warshalls アルゴリズムを使用したグラフ検索に取り組んでいますが、負のループを防ぐためにそれを変更する方法がわかりません。

私が入るとき：

コストマトリックスを取得します：

その後、負のエッジを追加してコストをさらに削減するため、クラッシュするまでループを開始します。

min は次のとおりです。

私の距離マトリックスには、コストがかからないところならどこでもINFがあります。

変更されたアルゴリズムが次のような古いトピックに出くわしました:

ただし、関数の代わりにこの修正を使用しても、ループが発生し、コストがさらに削減されます。この修正は正しいですか？そうでない場合、どのように書き直せばよいですか？ありがとう。

マトリックスを使用しdてグラフを表示します。d.(i).(j)と の間の距離を意味しiますj。vグラフ内のノード数を示します。

このグラフには負のサイクルがある可能性があります。

負のサイクルが存在するかどうかを確認したいと思います。Floyd-Warshallのバリエーションから次のように書きました。

私の質問は

1. 上記のコードは正しいですか？
2. part 1便利ですか？

私はこの関数を頻繁に呼び出すので、できる限り高速にしたいと考えています。だから私の3）質問は、他のアルゴリズム（特にBellman-Ford）がそれよりも速くなるかどうかです。

Floyd-Warshall アルゴリズムを見ています。

ページには、と書かれていますthe Floyd–Warshall algorithm assumes that there are no negative cycles。だから私の質問は、エントリーグラフが負の円を隠したらどうなるかということです. 出力は、dist負の円を隠している別のグラフを表しますか? part 1これは無効にならないのですか？

LR(1) クロージャーをすばやく計算するために、Warshall のアルゴリズムを実装しようとしています。

LR（0）でどのように機能するかを理解していると思います：

• グラフのノードは、次のようなLR アイテムです。A → B • C
• エッジは、から始まる「トランジション」ですA → B • C。C → • D

問題は、LR(1) には先読みの計算が必要であり、それらをアルゴリズムに組み込む方法がわかりません。与えられた LR アイテムの推移閉包を知っ
ていたとしても、各アイテムの先読みセットが何であるかを理解するためだけに、同じ計算をすべて行う必要があるように思えます。

ウォーシャルのアルゴリズムを使用して正規の LR(1) クロージャーを計算することは可能ですか?それとも、より制限されたケース (LR(0)、SLR(1) など) でのみ可能ですか?

MySQL ストアド プロシージャにウォーシャルのアルゴリズムを実装しました。残念ながら、手続きが完了するまでに時間がかかります。私はストアド プロシージャの作成の初心者です。高速化するために何ができるか知っていますか?

簡単な説明: 隣接リストの推移閉包を計算しようとしています。どのノードが接続されているかを知りたい (1 つのエッジで直接、または複数のエッジで間接的に)。例えば：

次の図は、グラフを示しています。

_{ウィキメディア・コモンズからの画像: https://en.wikipedia.org/wiki/File:Transitive-closure.svg}

SQL Fiddleまたはここでコードを表示できます。

1466 レコードのテーブルで手順を実行すると、私のコンピューターでは 45 秒かかります。