1

最大の重みを持つノード間の最短パスを見つけるコードが必要です。たとえば、A から D への最速のルートですが、重みが最大です。

  - B- --E
     /  \ /
    A    D
     \  / \
      C - -F

したがって、現時点で最も短いのは ABD または ACD です。重み付けが適用されると、コードは 2 つのパスから最長のパスを選択する必要があります (直感に反しますよね?)。

ダイクストラのアルゴリズムのアルゴリズムを変更しようとしていますが、最終的にはグラフ全体をトラバースするだけです。誰でもこれを行う方法を知っていますか? 自分でコーディングできるアルゴリズムだけでも、非常に役立ちます。

4

2 に答える 2

2
  1. グラフ上でソースからBFSを実行して ( とする)、 からターゲットsまでの最短経路の長さを見つけます。また、 -から任意のノードまでの距離をマークします。stdd(s,v)sv
  2. ソース ( ) からの距離が最大で-の場合にのみ、そのようなサブグラフG'=(V',E')を作成します。は、との両方が にある場合にのみに含まれます。GvV'sdd(s,v) <= de=(u,v)E'uvV'
  3. 新しいグラフG*=(V*,E*)を作成します。ここV'=V*で、エッジ(u,v)がANDにE*ある場合は、エッジがあります。E'd(s,u) < d(s,v)
  4. 新しい重み関数を設定し、を使用してBellman Fordをw*(u,v) = -w(u,v)実行します。G*w*
  5. Gfrom stoの最も重い最短パスtは weight-d(t)であり、BF によって検出されたパスは一致するパスです。

O(VE)Bellman-Ford がボトルネックであるため、アルゴリズムの時間計算量はです。

正しさの証明

主張 1: からsへの最短パスにtはサイクルが含まれていません。
証明は、サイクルを削除することで簡単になり、より短いパスが得られます。

主張 2: から へのすべての最短経路sはtにあるG'
証明: からsへのすべての最短経路tの長さは でdあり、 からの距離がsよりも長いノードdのみを削除したため、最短経路に不要なノードのみを削除します。

主張 3: からsへのすべての最短経路tは にありG*ます。
証明: 最短経路のいくつかのエッジを削除したと仮定(u,v)し、その経路を としますs->...->x->u->v->y->...->t。パスv->y->..->tの長さは(最小であると仮定して) でd-d(s,u)-1あることに注意してください。したがって、: - 矛盾から の最小性までの距離を持つパスがあります。d(s,u)
E*d(s,v) <= d(s,u)(u,v)s->...->v->y->...->tsd(s,v) + d-d(s,u)-1 <= d(s,u) + d - d(s,u) -1 <= d-1d

主張 4: にはサイクルがありませんG*。
証明: : に循環があると仮定しG*ますv1->v2->vk->v1。G' の定義により、すべてのノードは から到達可能ですs。d(s,v1)一般性を失うことなく、が他のすべてについて最小であると仮定しましょうd(s,vi)(そうでない場合は、この仮定に一致するようにインデックスを回転させます)。しかし、パス v1->v2->...->vk->v1 とd(s,v1)=d(s,v1). (vi,vi+1)これは、このパスの少なくとも 1 つのエッジを意味します。d(vi) >= d(vi+1)これは の構成と矛盾してE*おり、サイクルは G* に存在しません。

主張 5: アルゴリズムは正しい。

Bellman-Ford の正しさから、G*負のサイクルが含まれていない (サイクルがまったくない) ため、BF はw*inに従って最小の重みを持つパスを見つけますG*。wこのパスは、の構成から、に従って最大の重みを持つパスですw*。
のすべての最短パスGも (それらのみ) に存在するためG*、このパスはG最大の重みを持つ最短パスでもあります。

QED

于 2015-06-04T18:01:02.747 に答える
-1

重みを調整すれば、ダイクストラを使用できます。

最適なパスが最も少ないノードを訪問するものでなければならない場合は、各エッジをトラバースするために高いペナルティpを使用して、実際の重みを差し引くことができます。

    w ' = p − w

ペナルティは、ダイスクトラが機能しないw ' の負の値を防ぐために、最大の重みw maxよりも高く選択する必要があります。また、実際に最短パスが選択されるように、十分に高くする必要があります。nノードのグラフのpの適切な推定値は、次のようになります。

    p ≒ n・w最大

（編集：私の最初の答えは、代わりに実際の重みwの代わりに各エッジの相互重みw ' = 1/ wを使用することを提案しました。これは必ずしも最短経路を与えるわけではありませんが、少数のエッジを横断しながら重みが高い経路を提供します. この解法は多くの場合うまくいきません. しかし, 逆数を使わないペナルティ法とは完全に独立しています.)

于 2015-06-04T18:02:01.647 に答える