1

Floyd-Warshallアルゴリズムを実装しています。

約50ノードの完全グラフがあります。すべてのノード間の最大パスを見つけたいと思います。アルゴリズムが返すパスは、任意の長さ1 <x <50にすることができます。この長さは、最大で3〜4エッジの長さである必要があります。これを行うために、アルゴリズムを変更するにはどうすればよいですか？

4

1 に答える 1

1

iからjw(i,j)までの重みとします。次に、計算することができます

def shortest(w1, w2):
  w12 = a new V x V matrix
  for i in V:
    for j in V:
      w12(i, j) = w1(i, j)
      for k in V:
        if w12(i, j) > w1(i, k) + w2(k, j):
          w12(i, j) = w1(i, k) + w2(k, j)
  return w12

w2 = shortest(w, w)
w3 = shortest(w2, w)
w4 = shortest(w2, w2)

最後に、w4各ペアについて、最大4つのエッジを使用して開始から終了までの距離が含まれ、同様にw3。w4最初に計算せずに計算できることに注意してくださいw3。この形式の2値化を使用すると、つまり、すべての2乗行列を計算して組み合わせると、O（n³logk）の時間計算量、つまり最大パス長の対数のみを実現できます。

ウィキペディアには、上記で概説したアルゴリズムに関する短い記事があります。タイトルは「<ahref="https://en.wikipedia.org/wiki/Min-plus_matrix_multiplication" rel ="nofollow">min-plus行列乗算」です。おそらく、この用語、または代替用語「距離製品」に関連するいくつかの参照は、可能な実装に関する詳細情報につながるでしょう。たとえば、「<ahref="http://www.research.ibm.com/trl/people/yanagis/papers/RT0932.pdf"rel="nofollow">すべての人のためのより高速な面白い行列乗算」という論文があります。 -ペアの最短経路問題」では、この問題について説明し、いくつかのアルゴリズムを示し、SIMDの実装について検討します。

于 2013-05-07T00:02:41.097 に答える