Bellman-Ford算法在python中的實現

我正在爲Coursera上的「Graphs算法」課程做練習，我必須實現Bellman-Ford算法來檢測圖形是否有負循環，輸出1和0。我做了很多壓力測試，並且我的實現工作正常，但它在課程的一個測試用例中失敗（但除了「錯誤答案」，他們沒有提供任何有關它的信息）。我的實現與您在網上找到的完全一樣，因此我看不出我的代碼出了什麼問題。有任何想法嗎？Bellman-Ford算法在python中的實現

def relax(u,v,w,dist,prev): 
    if dist[u]+w < dist[v]: 
     dist[v] = dist[u]+w 
     prev[v] = u 

def bellmanFord(V,E): 
    dist = [float('inf')] * V 
    prev = [None] * V 
    dist[0] = 0 

    for i in range(V-1): 
     for edge in E: 
      relax(edge[0],edge[1],edge[2],dist,prev) 

    #checks for negative cycles   
    for e in E: 
     u = e[0] 
     v = e[1] 
     w = e[2] 
     if dist[u]+w < dist[v]: 
      return 1 

    return 0

來源

2017-01-07 tortov

他們不測試空圖，是嗎？ –

或者一個沒有強連接的圖？ –

輸入浮點或整數中的權重是多少？它保證圖形連接？ – kraskevich

此代碼不會爲沒有連接圖形工作例如，它提供了1以下的情況下這是正確的：

edges = [] 
edges.append([0, 1, 5]) 
edges.append([2, 3, -5]) 
edges.append([3, 4, -6]) 
edges.append([4, 2, -5]) 
edges.append([1, 2, 5]) 

print(bellmanFord(5, edges))

鏈接到演示：http://ideone.com/j8XAs3

，當我們去除邊緣1 - > 2它給它賦予0，即使圖形具有負週期（2 - > 3 - > 4 - > 2）：

edges = [] 
edges.append([0, 1, 5]) 
edges.append([2, 3, -5]) 
edges.append([3, 4, -6]) 
edges.append([4, 2, -5]) 

print(bellmanFord(5, edges))

鏈接到演示：http://ideone.com/N4Bljk

編輯：

正如你說，測試案例＃12你使用的每一個頂點作爲信號源後過去了，我相信，圖形是不接，問題在於解決方案的時間複雜度增加了，現在是O(n*n*m)，即大約10^11的操作肯定會超時。

所以，你可以修改算法，以下列方式：

1）找出所有連接的組件和分離出該組件的頂點和邊，並創建與頂點的新圖和邊緣

2）假設你現在有k個新的圖表，每個人都運行Bellman Ford。

此外，如果存在從每個頂點到每個其他可能頂點的路徑，則有連接的圖形會以錯誤的方式使用「強連通」一詞。

我看到了你所指的問題，我假設它是「問題：檢測貨幣匯率異常」，如果我對這個問題是正確的，那麼問題中給出的例子與它強烈連接的事實相矛盾因爲沒有辦法到達頂點4，但是圖形連接。

例中的問題：

不要讓我知道，如果不是你指的是這個問題，或者如果你有一些其他的疑惑。

來源

2017-01-07 15:35:18 uSeemSurprised

感謝您的回答uSeemSurprised。其實我錯了，所有的圖表都必須緊密聯繫。如果我理解的很好，Bellman-Ford算法是一種單源最短路徑算法，所以這意味着它只能找到連接到源的負循環。但是你的文章幫助我瞭解了這個問題。將BellmanFord函數應用於每個頂點作爲源，我能夠通過練習（＃12），上升到＃18，但失敗了，因爲它花費了太多時間。可能我的代碼沒有檢測到正確的距離，並在強連通的圖中留下了一些頂點。 – tortov

再次感謝您的回答。這是有問題的問題。我做了一個可達性函數，用組號來標記每個節點。所以在這個例子中，如果我從1開始，頂點1,2,3將被標記爲「0」，並且4將被標記爲「1」。如果開始是4，那麼每個人都將在組「0」上。在這兩種情況下，它的作品然後，我在ech組的第一個成員中運行bellmanFord。有了這個，我能夠通過案例＃12，但再次陷入案件＃18。這一次只花了0.13秒，得到了「錯誤的答案」。由於我花費的時間，我認爲它正在檢測一個假陰性週期。 – tortov

如果我按照相反的順序運行bellmanFord，從最後一組開始，程序再次在代碼＃12處失敗，但現在由於超時而失敗。如果它發現一個負循環，它立即返回，這就是情況＃18必須發生的事情。＃12和＃18都必須有大量的頂點和邊。無論如何，現在我必須找到一個使其失敗的測試用例。這裏是更新的代碼：[http://ideone.com/cczJjq]（http://ideone.com/cczJjq） – tortov

所以，我找到了鍛鍊的解決方案，它非常簡單。問題是使用float（'inf'）來初始化dist列表。相反，如果我使用一個龐大的數字，比如10000000，它可以在我的初始代碼上正常工作，而不需要掃描所有的頂點。它在一個沒有連接的圖的例子中起作用。感謝幫助，我學到了很多！

來源

2017-01-08 16:32:39 tortov

使用無窮始終是一個好主意，因爲您可能不知道值有多大，請嘗試在我提供的鏈接中給出的python代碼，它是一個非常乾淨的方式，鏈接：http://www.geeksforgeeks.org/dynamic-programming-set-23-bellman-ford-algorithm/ – uSeemSurprised

Bellman-Ford算法在python中的實現

回答

相關問題