21

以下は消費税です。

特定のグラフ問題では、頂点はエッジの重みの代わりに、またはエッジの重みに加えて重みを持つことができます。Cv を頂点 v のコストとし、C(x,y) をエッジ (x, y) のコストとします。この問題は、グラフ G の頂点 a と b の間の最も安価なパスを見つけることに関係しています。パスのコストは、パス上で遭遇するエッジと頂点のコストの合計です。

(a) グラフの各エッジの重みがゼロであると仮定します (エッジ以外のコストは ∞ です)。すべての頂点 1≤v≤n に対して Cv =1 であると仮定します (つまり、すべての頂点のコストは同じです)。 . a から b への最も安い経路とその時間計算量を見つけるための効率的なアルゴリズムを与えてください。

(b) ここで、頂点コストが一定ではなく (ただし、すべて正である)、エッジ コストが上記のままであるとします。a から b への最も安い経路とその時間計算量を見つけるための効率的なアルゴリズムを与えてください。

(c) ここで、エッジと頂点の両方のコストが一定ではないとします (ただし、すべて正です)。a から b への最も安い経路とその時間計算量を見つけるための効率的なアルゴリズムを与えてください。

これが私の答えです：

(a) 通常の BFS を使用します。

(b) ダイクストラのアルゴリズムを使用しますが、重みを頂点の重みに置き換えます。

(c)

ダイクストラのアルゴリズムも使用する

エッジの重みだけを考慮すると、ダイクストラのアルゴリズムの重要な部分は次のようになります。

if (distance[y] > distance[v]+weight) {
    distance[y] = distance[v]+weight; // weight is between v and y
}

ここで、頂点の重みについて考えると、次のようになります。

if (distance[y] > distance[v] + weight + vertexWeight[y]) {
   distance[y] = distance[v] + weight + vertexWeight[y]; // weight is between v and y
}

私は正しいですか？

(c) に対する私の答えは単純すぎると思いますね。

4

2 に答える 2

19

あなたは正しい道を進んでおり、解決策は非常に簡単です。

B、C の両方で、問題を通常のダイクストラに減らします。これは、頂点に重みがないことを前提としています。
このためにはw':E->R、エッジの新しい重み関数 を定義する必要があります。

w'(u,v) = w(u,v) + vertex_weight(v)

(b) w(u,v) = 0(または const) で、解は (c) にも適合するようにロバストです!

その背後にある考え方は、エッジを使用すると、エッジの重みと、ターゲットの頂点に到達するためのコストがかかるということです。ソースのコストは既に支払われているため、無視します1。

アルゴリズムを変更する代わりに、問題を減らすことは、通常、使用、証明、および分析がはるかに簡単です!.

（1）このソリューションでは、ソースの重みを「逃す」ため、からへの最短経路は次のsようになりtます。dijkstra(s,t,w') + vertex_weight(s)_dijkstra(s,t,w')stw'

于 2012-05-04T17:06:23.800 に答える
4

頂点の重みは、2 つの頂点 a1 と a2 のすべての頂点 a を、a1 から a2 へのエッジで a の重みでスライスすることによって削除できます。

ダイクストラのアルゴリズムの適応については、あなたが正しいと思います。

于 2012-05-04T17:13:07.620 に答える