-1

私自身の問題：

G を n 個の頂点と m 個の辺を持つ無向グラフとします。
v_1 から v_2 までのリストがありますが、今は重要ではありません。
すべてのエッジの重みは X に等しくなります。
私たちのタスクは、v_i から v_j への最速パスが w = 2X であるすべてのペア (v_i、v_j) を見つけることです。

(例を見てください)

ブルートの v * dikstra や v*v よりも高速に実行できますか?? この問題は O(n^2) 時間で解けるでしょうか? どのアルゴリズムが最適でしょうか? いつも助けてくれてありがとう。

例：

    n = m = 5
    v_1 -> v_2 -> v_3 -> v_4 -> v_5 and v_1 -> v_3

解決：

(1,4)、(2,4)、(3,5)

写真: http://i.stack.imgur.com/rVhee.gif

v_1 から v_4 への最短パスは 2X です (別のソリューションと同じ)。

編集:隣接リストがあります。

4

1 に答える 1

1

ブルートの v * dikstra や v*v よりも高速に実行できますか?? この問題は $O(n)$ または $O(n log n)$ 時間で解決できますか?

出力には次のような異なるエントリが含まれる可能性があるため、 O(n^2)( = )よりも良くなることはありません。O(v*v)O(n^2)

          a
          |
     b----c----d
          |
          e

ソース/ターゲット = c の場合を除き、すべての頂点からすべての頂点への長さ 2 のパスがあります。このグラフを一般化するO(n^2)と、必要な距離を持つペアが得られます

于 2012-10-18T17:41:24.370 に答える