在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节点的传出边缘。

但是，如果您需要非常快速的算法，您必须对其进行优化。但我认为这是另一个话题。此外，看起来没有人对硬优化感兴趣。
我可以快速添加，只需简单的优化就可以忽略相应的远端顶点。在数组中，您可以通过简单的方式计算距离，所以它是令人愉快的优化。
我还没有提到知道优化，因为我相信他们都在网络的随机过程。