有向巡回グラフのすべてのノードをカバーする最短経路を見つけるにはどうすればよいですか？

Question

1つのノード からの有向循環グラフの最短経路の例が必要です（入力になるノードからグラフのすべてのノードに到達するはずです）。

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

Answer 1

EDIT：問題を誤解しています。これを拾うために@jfclavetteに感謝します。古い答えは最後です。

あなたが解決しようとしている問題は、Travelling salesman problemと呼ばれています。 potential solutionsがたくさんありますが、NP完全なので、大きなグラフを解くことはできません。

旧答：あなたが見つけるためにしようとしている何

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

Answer 2

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

重み付きグラフの場合、bellman-Fordアルゴリズムを使用できます。サイクルを検出することもできます。

Answer 3

重み付けされていない場合：Breadth first search。 重み付けの場合：Dijkstra's。擬似コードで

Answer 4

：

//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) 

これは各頂点にダイクストラのわずかに異なるが実行されます。突然変異したDijkstras にはいくつかの重要な違いがあります。最初に、すべての初期距離は∞に設定されます。 開始頂点でさえあります。第2に、最初に開始点をキューに入れる必要があります。 はすべて優先順位が同じであるため、最初にオフにすることを確認してください。最後に、 突然変異したDijkstrasは、開始ノードまでの距離を返します。開始点に戻る パスがなかった場合、距離は∞のままです。これらのすべての最小値は、突然変異したDijkstrasから返された が最短経路です。 DijkstrasはO（| V |^2）で最悪で を実行し、min_cycleはこの形式のDijkstras | V |を実行します。最後の実行時間はO（| V |^3）となる。 min_cycが ∞を返した場合、グラフは非周期的です。

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