實現Dijkstra後2個節點之間的圖中的所有路徑

我正在研究一個巨大的光網絡項目，其中網絡被表示爲可能存在週期的無向圖。在某個點上，我想要查找圖中兩個節點之間代表任意光學連接的所有最小跳躍路徑。我成功實現了所有邊的權重爲1的Djikstra，以找到最小跳躍路徑而不是最小權重，並修改鬆弛步驟來保存節點的所有父節點而不是一個節點（當距離相等而不是較小時，添加代碼以保存）。因此，現在在下面的示例網絡中，我已經從節點0到節點4：節點1具有父節點0，節點2具有父節點0，節點3具有父節點1,2並且節點4具有父節點3.每個節點組合是對象單元在一個二維數組中，每個單元格的許多屬性之一是其父項的一個列表（也就是說，當從0到3時，在單元格0,3中搜索父項時給出了3的父項）實現Dijkstra後2個節點之間的圖中的所有路徑

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

現在我卡住了。我想以某種方式保存從所有源到圖中所有目標的所有最小跳躍路徑，這樣我就可以爲任何可能的任意連接提供最小跳躍路徑。你能推薦一個解決方案嗎？我正在努力工作好幾天，而且我真的陷入了困境。預先感謝您。

來源

2012-10-21 user1762882

「作爲無向」和「節點1具有父0」有在本絲束東西不相容性。 –

圖表有多大？以及頂點和邊的數量之間的近似比例是多少？ – Serge

@Serge是的，我誤解了。他正在路由;我把我的評論刪除了。 – LSerni

您的主要問題是要存儲。

假設您有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算法的下一跳：從第一個節點開始，並探索存儲在每個節點中的整個圖表與第一個節點的距離，以及提供該距離的前一個節點。最後，元組{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-21 11:02:06 LSerni

實現Dijkstra後2個節點之間的圖中的所有路徑

回答

相關問題