Belman卡拉巴算法解釋

Question

貝爾曼福特和這個有什麼區別嗎？

有人可以解釋如何實現這一點，以找到給定節點之間的最長路徑？ 我知道該算法計算兩個節點之間的最短路徑，所以如果有人可以解釋如何實現，我可以弄清楚如何修改它以便給我最長的路徑。

Answer 1

我在回答這個問題，以防別人將來會有同樣的問題。

我發現了一個python實現（不幸的是它沒有記錄，我仍然在玩它，試圖完全理解它）。

這將計算一個給定節點和圖中所有其他節點之間的最短路徑。

from json.encoder import INFINITY 
def BellmanKalaba(v,x,m): 
    L=list() 
    iteration=list() 
    for j in range(len(v)): 
     iteration.append(v[x][j]) 
    L.append(iteration) 
    k=0 
    while True: 
     iteration=[0 for i in range(len(v))] 
     for j in range(len(v)): 
      minim=INFINITY 
      for i in range(1,len(v)): 
       a=L[len(L)-1][i]+v[i][j] 
       if a < min: 
        minim=a 
      iteration[j]=minim 
     k+=1 
     L.append(iteration) 
     if iteration==L[len(L)-1]: 
      return L 
     if k==m: 
      return 0 

v是一個表示加權圖的矩陣， x是開始節點， m是邊緣的數目。

現在，這變得有點怪異，因爲L實際上包含2個列表，所以從x到y的最短路徑將是min(L[0][y], L[1][y]). 我無法解釋它究竟是如何工作的。 此外，這不適用於任何給定的圖表。

這是一個開始，也許現在有人可以跳進來幫忙。