0

G = (V;E) を有向グラフとし、その辺はすべて非負の重みを持ちます。s,t を V の 2 つの頂点、e を E の辺とする。s から t へのすべての最短経路が辺 e を含むかどうかを判定するアルゴリズムを説明してください。

さて、これがダイスクトラの時間計算量を達成する方法です: s からダイクストラを実行し、delta(s,t) (s から t への最短経路の重み) を計算するだけです。エッジ e を削除し、新しいグラフの s から Djikstra を再度実行します。新しいグラフの delta(s,t) が増加した場合、s から t へのすべての最短経路にエッジ e が含まれていることを意味します。それ以外の場合は正しくありません。

この問題を解決するためのより効率的なアルゴリズムがあるかどうか疑問に思っていました。ダイクストラの時間計算量を超えることは可能だと思いますか?

前もって感謝します

4

1 に答える 1

1

あなたのアプローチは私には正しいように聞こえます。エッジ e を取る可能性がある場合とない場合の最短経路を計算するだけです。これにより、2 つのダイクストラ検索が得られます。

A*、双方向検索、またはダイクストラ検索ツリーの回復に行く場合、改善の余地があります。

  • A* は Dijkstra-query を高速化しますが、残りの距離に適切な境界を定義できる必要があるため、グラフでは不可能な場合があります。
  • 双方向の検索は、両方の検索がエッジで出会うことで実行できます。次に、非常に類似した 2 つの完全な Dijkstra を使用する代わりに、1 つの高速双方向クエリ + 両方のケースで追加の作業を行うだけで、エッジの有無にかかわらずすべてのパスを調べることができます。
  • エッジなしで一度検索し、検索ツリーを維持できます。次に、e を追加し、e の始点から始まる最短パス ツリーを更新します。終点のラベル > 始点のラベル + 長さ e の場合、e を使用するとより早く終点に到達できます。エンドポイントの近隣を再帰的に検索し、以前よりも速く到達できる場合にのみ距離を更新します。いくつかの作業を節約する必要があります。
于 2013-03-04T09:57:37.713 に答える