6

あるノードからの有向巡回グラフの最短経路の例が必要です (入力となるノードからグラフのすべてのノードに到達する必要があります)。

例があれば、C ++またはアルゴリズムで必要です。

4

4 に答える 4

7

編集：おっと、質問を読み間違えました。これを拾ってくれてありがとう@jfclavette。古い答えは終わりです。

あなたが解決しようとしている問題は、巡回セールスマン問題と呼ばれています。考えられる解決策はたくさんありますが、NP完全であるため、大きなグラフを解くことはできません。

古い答え：

あなたが見つけようとしているものは、グラフの周囲と呼ばれます。これは、ノードからそれ自体までの距離を無限大に設定し、Floyd-Warshallアルゴリズムを使用することで解決できます。その場合、ノードiからの最短サイクルの長さは、位置iiのエントリになります。

于 2009-04-25T15:56:06.340 に答える
4

重み付けされていない場合:幅優先検索。加重の場合:ダイクストラの.

于 2009-04-27T10:55:11.663 に答える
3

擬似コード:

//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 が ∞ を返す場合、グラフは非巡回です。

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

于 2010-10-20T04:34:47.677 に答える
1

重み付けされていないグラフの場合、BFS がその役割を果たします。グラフには潜在的なサイクルがあるため、訪問したノードを追跡する必要があります (とにかく BFS に対してこれを行う必要があります)。

加重グラフの場合、ベルマン・フォード アルゴリズムを使用できます。また、サイクルを検出することもできます。

于 2009-04-25T22:49:28.873 に答える