サイクル指向の最短経路グラフ

Question

私は有向グラフサイクルの最短経路を1つのノード（アノードからグラフの全ノードに届くはずです）の例が必要です。 C++またはアルゴリズムありがとうございました.........

Answer 1

あなたはそれのためにminimum spanning treeを見つける必要があります。

ウィキペディアの有向グラフでは、thisアルゴリズムを使用できます。擬似コードで

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) 

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

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