path - サイクル有向グラフの最短経路

Question

1つのノードで有向グラフサイクルの最短経路の例が必要です（アノードからグラフのすべてのノードに到達する必要があります）例があれば、c++またはアルゴリズムで必要です... .....。。。

Answer 1

そのための最小スパニング ツリーを見つける必要があります 。

ウィキペディアによる有向グラフの場合、このアルゴリズムを使用できます。

Answer 2

擬似コード:

//INPUT: graph G = (V,E)
//OUTPUT: shortest cycle length
min_cycle(G)
  min = ∞
  for u in V
    len = dij_cyc(G,u)
    if min > len
      min = len
  return min    

//INPUT: graph G and vertex s
//OUTPUT: minimum distance back to s
dij_cyc(G,s)
  for u in V
    dist(u) = ∞
                   //makequeue returns a priority queue of all V
  H = makequeue(V) //using dist-values as keys with s First In
  while !H.empty?
    u = deletemin(H)
    for all edges (u,v) in E
      if dist(v) > dist(u) + l(u,v) then
        dist(v) = dist(u) + l(u,v)
        decreasekey(H,v)

  return dist(s)

これにより、各頂点でわずかに異なるダイクストラが実行されます。突然変異したダイクストラには、いくつかの重要な違いがあります。まず、最初の頂点も含めて、すべての初期距離が ∞ に設定されます。第 2 に、開始頂点はすべて同じ優先度を持つため、最初にオフになることを確認するために最初にキューに配置する必要があります。最後に、変異したダイクストラは開始ノードまでの距離を返します。開始頂点に戻る経路がない場合、距離は ∞ のままです。突然変異したダイクストラからのこれらすべての戻り値の最小値が最短経路です。Dijkstras は最悪でも O(|V|^2) で実行され、min_cycle はこの形式の Dijkstras |V| で実行されるため、最短のサイクルを見つけるための最終的な実行時間は O(|V|^3) です。min_cyc が ∞ を返す場合、グラフは非巡回です。

最短サイクルの実際のパスを返すには、わずかな変更のみが必要です。