問題タブ [bellman-ford]

Prim のアルゴリズムと有向グラフの最短経路を計算する Bellman-Ford アルゴリズムを使用して、有向グラフで最小スパニング ツリーを見つける方法を学習するためのリソースを提案してください。

ダイクストラまたはベルマンフォードのアルゴリズムを使用して、特定の頂点に移動した場合にエッジの一部が影響を受けるグラフの最短経路を見つけるにはどうすればよいでしょうか。そのため、影響を受けるエッジの長さは、元の長さよりも長くなったり短くなったりします。

有向グラフで負の重みサイクルを見つけるアルゴリズムについて考えていました。問題は次のとおりです。グラフG（V、E）があり、負の重みを持つサイクルを見つけるための効率的なアルゴリズムを見つける必要があります。このPDFドキュメントのアルゴリズムを理解しています

簡単に言うと、このアルゴリズムは、| V | -1回反復して緩和を行うことにより、ベルマンフォードアルゴリズムを適用しています。その後、さらにリラックスできるエッジがあるかどうかをチェックし、負の重みサイクルが存在し、親ポインターによってそれをさかのぼることができ、すべてがうまくいくと、負の重みサイクルが見つかります。

ただし、グラフ上で深さ優先探索（DFS）を使用して、移動した距離のこれまでの合計を追跡する別のアルゴリズムを考えていました。最初はすべてのノードを白でマークし、私がいるときは灰色にします。パスを検索し、終了時に黒でマークします。これにより、訪問したノードが見つかり、それが（パス内で）灰色であり、深さによってすでに終了している黒ではない場合にのみ、サイクルが見つかることがわかります。 -最初の検索なので、私のアルゴリズムでは、すでにアクセスした灰色のノードに到達した場合、更新内容（新しい距離）を確認し、以前よりも低い場合は、負の重みがあることがわかりますサイクルし、それをさかのぼることができます。

私のアルゴリズムは間違っていますか？もしそうなら、あなたは反例を見つけることができますか？そうでない場合は、私がそれを証明するのを手伝ってくれませんか？

ありがとうございました

パスが存在する場合、正確にk個のエッジを持つグラフで、sからtまでの2つの頂点からのパスを見つけるアルゴリズムを探しています。

また、複数のパスが見つかった場合は、単一のエッジの最大重みが最小のパスが優先されます。（全体の重みではありません）。

例：K=5と言います

パス1：s --a --b --c --d --t（重み1 -1 -1 -10 -1）

パス1の最大の重みは10です。

パス2：s --x --y --z --w --t、重み7-9-8-6-7

パス2の最大の重みは9であるため、これが推奨されます。

この問題をどの程度正確に解決できますか？

Bellman fordアルゴリズムについては以下のページを参照してください（例を示します）。 http://compprog.wordpress.com/2007/11/29/one-source-shortest-path-the-bellman-ford-algorithm

まだわかりません。外側のループの最初のループ反復では、例で言うと、最初にエッジ 1->2 とエッジ 1->4 を変更します。エッジ 2->3、2->5、4- を緩和する際の問題は何ですか? d[2] と d[4] があるため、同じステップで >3、4->5 です。

頂点 z から始まるベルマンフォード アルゴリズムを実行する必要がある宿題をやっています。「各パスで、図と同じ順序でエッジを緩和し、各パスの後に d と pi の値を表示する」ように求めています。私が理解していることから、このアルゴリズムは BFS のようにグラフをトラバースすると考えました。これは、使用してほしい図から理解できるので、同じパスがどのように機能するかわかりません。誰かが開始方法を指摘して正しい方向に向けることができれば、非常に役立ちます。質問、および質問が参照している図:

問題を（グラフで）解決するためにベルマンフォードアルゴリズムを実装しましたが、この解決策は遅すぎたため、ベルマンフォードのキューをヒープ（std :: set）に置き換えたため、最短の解決策になりましたパスがより速く見つかります。（ダイクストラアルゴリズムはどういうわけか近い）

ここで、ノード番号をヒープに挿入します。これにより、デフォルトのstd :: setは、コストではなく番号を使用してノードを並べ替えます。すべてが順調であり、アルゴリズムは正しい答えを与えます。

std :: setのカスタム比較関数を実装すると、ノードは番号ではなく距離で並べ替えられ、アルゴリズムは残りのノードまでの最短距離を提供しなくなります。

これは私の比較関数です：

したがって、BFアルゴリズムであるため、アルゴリズムは改善ができなくなるまで実行されます。比較関数はどういうわけかstd::setを「混乱」させることができますか？これが、この比較関数を追加すると間違った答えが得られる理由がわかる唯一の理由です...

つまり、ノードが完全にランダムな順序である場合は機能するのに、コスト順に並べられている場合は機能しないのはなぜですか...

正と負のエッジを持つ有向グラフで、ソースから宛先への最短パスを見つけます。パスのどのポイントでも、負になる前に来るエッジの合計がありません。そのようなパスが存在しない場合は、それも報告してください。

修正されたベルマンフォードを使用しようとしましたが、正しい解決策が見つかりませんでした。

いくつかのポイントを明確にしたいと思います：

1. はい、負の体重サイクルが存在する可能性があります。
2. nはエッジの数です。
3. 問題に解決策がある場合は、O（n）の長さのパスが存在すると想定します。
4. + 1/-1エッジウェイト。