アルゴリズムに関するセジウィックのコースからこの質問があります。「クリティカル エッジ。エッジに重み付けされた有向グラフが与えられた場合、その除去が からへE*log(V)の最短経路の長さの最大増加 (おそらく無限) を引き起こすエッジを見つけるアルゴリズムを設計します。仮定します。すべての辺の重みは厳密に正です (ヒント: から への最短経路距離を計算し、削減されたコストを考慮してください)。std(v)svc′(v,w)=c(v,w)+d(v)−d(w) ≥ 0
O(E + V*log(V))私はインターネットで、1989 年に 3 人の男が高度なデータ構造を必要とする複雑なアルゴリズムを思いついたことを読んだことがあります。このアルゴリズムを開発するのに 3 人の高度なコンピューター科学者がいるとしたら、入門コースとしては難しすぎませんか? しかし、おそらくそれはただのほうがはるかに簡単ですO(E*log(V))。
それを解決するのを手伝ってもらえますか? 質問のヒントがわかりません。
これは、セッジウィックのヒントに基づいて、最短経路上のクリティカル エッジを見つけるアルゴリズムのスケッチです。
まず、削減されたコストc'(v,w)=c(v,w)+d(v)−d(w)は、 vをちょうど通過するときの sからwへの最短経路の長さの増加に対応します。wの前。( vがsからwへの最短経路にある場合、この増加は 0 です。) (実際、d(v) は s から v への最短経路の長さであり、c(v, w) は v から w に移動するためのコストです。 w.)
sからtへの最短経路が(s, ..., v, t)であり、最後のエッジ(v, t)を削除するとします。次に、 sからtまでの最短経路の長さの増加は、u != vで、すべてのエッジ(u, t)のc'(u, t)の最小値に等しくなります。
uがc'(u, t)が最小であるとします (それでもu != v )。次に、sからuへの最短経路を逆方向にたどり、 sからtへの最短経路に属する頂点 (たとえばw )に到達するまで(エッジを削除せずに) たどります。sからtへの最短経路は(s, ..., w, ..., v, t) のようなものです。
wとtの間のエッジを削除すると、最短経路でc'(u, t) の最大増加が得られることに注意してください。実際、wとtの間のエッジの 1 つが欠落している場合は、頂点uを通ってwからtに移動するだけで十分です。一方、最後のエッジ(v, t)を削除すると、まさにこの増加が生じることに注意してください。
さて、tで行われたことをwで繰り返すだけです。c'(x, w)が最小で、xが最短経路上にないような頂点xを見つけます。sからwへの最短経路に属する頂点に到達するまで、 sからxへの最短経路を逆方向にたどります。
sに達すると、最短パスの長さを最大に増加させるために削除する頂点を決定できます。
これは紛らわしい質問です、同意します。ここに私の考えがあります。
「削減されたコスト」という用語と定義は、元のコストを削減されたコストで置き換えることにより、 A* 検索アルゴリズムをダイクストラのアルゴリズムに削減するときに使用されます。
c′(v,w) = c(v,w) - h(v) + h(w) = c(v,w) - (h(v) - h(w)) > 0
パーツはヒューリスティック関数のh(v) - h(w)ドロップであり、一貫性のある (単調な) ヒューリスティックの場合、エッジ コストを超えてはならないため、削減されたコストは依然として 0 よりも大きくなります (スライド 14 と 15 を参照) 。
Sedgewick は、元の からへの元の最短パスに沿ってエッジが 1 つ削除されているが、元の と同じであるd(v)新しい/置換の最短パスを検索するときに、一貫したヒューリスティックとして元の距離関数 ( )を使用することを提案しているようです。個人的には、最も重要なエッジの問題を解決するのにどのように役立つかわかりません。G'GstO(ElogV)
同様の問題もあります。グラフ内のすべての下向きおよび上向きのクリティカル エッジを見つけます。定義上、下降クリティカル エッジのコストを削減すると、全体的な SP コストが削減されます。上向きのクリティカルエッジのコストを増やすと、全体の SP コストが増加します。すべてのクリティカル エッジは にありO(ElogV)ます。ch.8 を参照してください。しかし、これはどのエッジが最も重要であるかという質問には答えません (削除すると最大 SP が増加します)。
お気づきのように、最も重要なエッジの問題は、Malik、Mittal、および Gupta (1989) によって
O(E + V*log(V))時間内に解決されました。元の MMG 論文は見つかりませんでしたが、このプレゼンテーションはそれを非常によく説明しています。私が見る限り、優先キューで解決でき、特定のデータ構造は必要ありません。
元の質問 (削減されたコストを使用した有向グラフの最も重要なエッジの解決策) に実際に答えていないことを申し訳ありませんが、上記のリンクと考えが誰かにとって役立つことを願っています. Sedgewick が意味する解決策を見て喜んでいます。