在2D陣列Belman-Ford算法

Question

我有一個問題，施加Bellman-Ford算法到2D陣列（未於圖）

輸入陣列具有米 X Ñ尺寸：

  s[1,1] s[1,2] ... s[1,n] -> Exit 
      s[2,1] s[2,2] ... s[2,n] 
      ... 
Entry -> s[m,1] s[m,2] ... s[m,n] 

它是房間一樣（每個入口是一個房間s [x，y]入場費）。每個房間也可能有負成本，我們必須找到從進入選擇房間和退出最便宜的路徑。

例如，我們已經有了這個數組客房和費用：

1 5 6 
2 -3 4 
5 2 -8 

我們希望能夠走過去室[3,2]，S [3,2] = 4。我們開始形式在[1,3]，必須走過去[3,2]我們去[3,3]之前。

而我的問題是，在貝爾曼福特算法中實現它的最佳方法是什麼？我知道Dijkstry算法不會因負成本而工作。

對於[0，maxHeight]中的每個房間是否正確並放鬆所有鄰居？像這樣：

for (int i = height-1; i >= 0; --i) { 
     for (int j = 0; j < width; ++j) { 
      int x = i; 
      int y = j; 
      if (x > 0) // up 
       Relax(x, y, x - 1, y); 
      if (y + 1 < width) // right 
       Relax(x, y, x, y + 1); 
      if (y > 0) // left 
       Relax(x, y, x, y - 1); 
      if (x + 1 < height) // down 
       Relax(x, y, x + 1, y); 
     } 
    } 

但是，我該如何讀取費用選擇房間，從房間到退出？

Answer 1

如果您知道如何從數組中移動圖形，則可以滾動到附加條件段落。另請閱讀下一段。

事實上，你可以像在圖表上看那座建築。

你可以看到這樣的：（我忘了門在第二行，對不起。）

那麼，它是如何可能的是實施。暫時忽略其他條件（離開前訪問特定頂點）。
重量函數：
讓S[][]是一個入口成本數組。請注意，關於邊的權重只會決定最終的頂點。無論是(1, 2) -> (1,3)還是(2,3) -> (1, 3)。成本由第二個頂點定義。這樣的功能可能看起來像：

cost_type cost(vertex v, vertex w) { 
    return S[w.y][w.x]; 
} 
//As you can see, first argument is unnecessary. 

邊緣：
其實你不必把所有邊緣的一些陣列。您可以在每次需要時使用函數計算它們。 如果該節點存在，頂點(x, y)的鄰居是(x+1, y),(x-1, y),(x, y+1), (x, y-1)。你必須檢查它，但它很容易。 （檢查是否new_x> 0 & & new_x < max_x。）它可能看起來像：

//Size of matrix is M x N 
is_correct(vertex w) { 
    if(w.y < 1 || w.y > M || w.x < 1 || w.x > N) { 
     return INCORRECT; 
    } 
    return CORRECT; 
} 

生成的鄰居可以看起來像：

std::tie(x, y) = std::make_tuple(v.x, v.y); 
for(vertex w : {{x+1, y}, {x-1, y}, {x, y+1}, {x, y-1}}) { 
    if(is_correct(w) == CORRECT) {//CORRECT may be true 
     relax(v, w); 
    } 
} 

我相信，它不應該採取額外的內存四個邊緣。如果您不知道std::tie，請查看cppreference。 （額外變量x，y需要更多的內存，但我相信，這是更具可讀性這裏。在您的代碼可能不會出現。）

很明顯，你必須有一個與距離等二維數組和（如有必要）的前身，但我認爲這很清楚，我不必描述它。

附加條件：
你想知道，從進入到退出的成本，但你必須訪問一些頂點compulsory。計算它的最簡單方法是計算從enter到compulsory和從compulsory到exit的成本。 （將有兩個單獨的計算。）它不會更改big O時間。之後，您可以添加結果。

你只需要保證不可能在compulsory之前訪問exit。很容易，你可以通過在is_correct函數中添加額外的行來擦除exit的輸出邊緣（然後將需要頂點v），或者生成鄰居代碼片段。

現在您可以實施它basing on wikipedia。你有圖表。

爲什麼你不應該聽？
更好的方法是從其他頂點使用貝爾曼福特算法。注意，如果你知道從A到B的最佳路徑，你也知道從B到A的最佳路徑。爲什麼？總是必須爲最後一個頂點支付費用，而且您不必先付款，這樣您就可以忽略它們的成本。休息很明顯。
現在，如果您知道您想知道路徑A-> B和B-> C，則可以使用節點B的一次BF和反向路徑B-> A計算B-> A和B-> C。結束了。
您只需擦除entry和exit節點的傳出邊緣。

但是，如果您需要非常快速的算法，您必須對其進行優化。但我認爲這是另一個話題。此外，看起來沒有人對硬優化感興趣。
我可以快速添加，只需簡單的優化就可以忽略相應的遠端頂點。在數組中，您可以通過簡單的方式計算距離，所以它是令人愉快的優化。
我還沒有提到知道優化，因爲我相信他們都在網絡的隨機過程。