algorithm - 正の重みを持つ有向グラフで最短の長さのサイクルを見つける

Question

インタビューでこの質問をされたのですが、まともな答えが思いつきませんでした。そこで、すべてのサイクルを見つけてから、最も短いサイクルを選ぶという素朴なアプローチを彼らに伝えました。

この問題の効率的な解決策を知りたいです。

Answer 1

Floyd-Warshall アルゴリズムは簡単に変更できます。(グラフ理論にまったく精通していない場合は、アルゴリズムの紹介のコピーを取得するなど、チェックすることをお勧めします)。

伝統的に、あなたpath[i][i] = 0はそれぞれのために始めますi。ただし、代わりに から開始することもできますpath[i][i] = INFINITY。いずれにせよ、これらのゼロは計算で使用されていないため、アルゴリズム自体には影響しません (またはのパスpath[i][j]は変更されないため)。k == ik == j

最後にpath[i][i]、最短のサイクルが通過する長さiです。min(path[i][i])したがって、すべてのを見つける必要がありますi。また、サイクル自体 (長さだけでなく) が必要な場合は、通常のパスで通常行われるのと同じようにk、アルゴリズムの実行中に記憶することで実行できます。

さらに、ダイクストラのアルゴリズムを使用して、特定のノードを通過する最短のサイクルを見つけることもできます。この修正された Dijkstra をノードごとに実行すると、Floyd-Warshall と同じ結果が得られます。また、各ダイクストラはであるため、全体的な複雑さO(n^2)は同じになります。O(n^3)

Answer 2

疑似コードは、ダイクストラのアルゴリズムを単純に修正したものです。

for all u in V:
   for all v in V:
      path[u][v] = infinity

for all s in V:
   path[s][s] = 0
   H = makequeue (V) .. using pathvalues in path[s] array as keys
   while H is not empty:
      u = deletemin(H)
      for all edges (u,v) in E:
         if path[s][v] > path[s][u] + l(u, v) or path[s][s] == 0:
            path[s][v] = path[s][u] + l(u,v)
         decreaseKey(H, v)

lengthMinCycle = INT_MAX

for all v in V:
   if path[v][v] < lengthMinCycle & path[v][v] != 0 :
      lengthMinCycle = path[v][v]

if lengthMinCycle == INT_MAX:
   print(“The graph is acyclic.”)

else:
   print(“Length of minimum cycle is ”, lengthMinCycle)

時間の複雑さ: O(|V|^3)

Answer 3

• DFS を実行する
• DFS 中にエッジのタイプを追跡する
• エッジのタイプはTree Edge、Back Edge、Down EdgeおよびParent Edge
• を取得したときに追跡し、Back Edge長さを取得するための別のカウンターを用意します。

詳しくAlgorithms in C++ Part5 - Robert Sedgwickはこちら

Answer 4

あなたがしなければならないことは、常に 1 である各ノードに別の重みを割り当てることです。これらの重みを使用して、あるノードから同じノードへの最短経路アルゴリズムを実行します。ただし、中間のパスを考慮する場合、実際の重みが負のパスは無視する必要があります。