1

私は、サイクルが存在する可能性がある無向グラフとしてネットワークが表される巨大な光ネットワーク プロジェクトに取り組んでいます。ある時点で、任意の光接続を表すグラフ内の 2 つのノード間のすべての最小ホップ パスを見つけたいと考えています。すべてのエッジに重み 1 の Djikstra を実装して、最小重みの代わりに最小ホップ パスを見つけ、緩和ステップを変更して、ノードのすべての親を 1 つではなく保存するようにしました (距離がちょうど小さいのではなく等しいときに保存するコードを追加しました)。したがって、以下のネットワーク例では、ノード 0 からノード 4 に移動しています。ノード 1 には親 0 があり、ノード 2 には親 0 があり、ノード 3 には親 1,2 があり、ノード 4 には親 3 があります。各ノードの組み合わせはオブジェクト セルです。 2 次元配列で、各セルの多くの属性の 1 つはその親のリストです (つまり、セル 0 で親を検索し、

0 ---- 1
|      |
2 ---- 3 --- 4

今、私は立ち往生しています。グラフ内のすべてのソースからすべての宛先へのすべての最小ホップ パスを保存して、可能な任意の接続に最小ホップ パスを提供できるようにしたいと考えています。これに対する解決策をお勧めできますか？私は何日もそれに取り組んでいますが、本当に立ち往生しています。前もって感謝します。

4

1 に答える 1

0

あなたの主な問題はストレージになるでしょう。

10000 個のノードがあるとします。次に、各ノード N(i) について、考えられるすべての宛先への次の最小ホップを格納します。これは、グラフのノードごとに 9999 個のノードがあることを意味します。つまり、3*N^2 個のノード値を格納する必要があります。

その時点で、ノード N(i) からノード N(j) に移動することは、次のことを意味します。

k = i
while k is not j:
    h = 0
    while h < length(N(k).NextHops)
        if N(k).NextHops(h).Destination is j:
           k = N(k).NextHops(h).NextNode
           break
        else:
           h = h+1
    # if h == length of NextHops, "No Route To Host"

Dijkstra を使用して NextHops を初期化できます (最短パスが見つかったら終了しません)。最初のノードから開始し、各ノードに最初のノードまでの距離を格納するグラフ全体を調べ、その距離を提供する前のノードを調べます。最後に、タプル { Dest: i; 料金： ？; 次： ？} はすべてのノードに対して初期化されます。グラフが接続されている場合、各ノードに N-1 個のエントリがあるため、配列の位置 i で 2 タプル { Cost, Next } を使用できます。

接続されたグラフの場合、ルート検索アルゴリズムは次のようになります

def findpath(i, j):
    k = i
    p = []
    c = 0
    while k is not j:
        p += i
        c += N[k].NextHops[j].Cost
        k =  N[k].NextHops[j].Next

    return { 'path': p, 'cost': c }
于 2012-10-21T11:02:06.100 に答える