Belman-Ford算法在2D数组中

Question

我在将贝尔曼-福德算法应用于二维数组（而不是图形）时遇到了问题。

输入数组具有 m x n 的尺寸：

           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]的5开始，并必须在前往[3,3]之前走过[3,2]。

我的问题是，在Bellman-Ford算法中实现它的最佳方法是什么？我知道Dijkstra算法由于负成本而无法使用。

对于每个高度范围内的房间 [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);
        }
    }

那么我该如何查看选定房间的费用以及从房间到出口的路线？

- Michał Wiatr

---

如果你想知道最优成本，你必须保存最优路径。你已经知道你要走哪个方向（你的if语句），所以在你走的时候只需保存这些信息即可...我认为你不能仅使用你的二维数组来保存这些数据，你必须使用另一个二维数组或者只是添加字段到你当前的二维数组。你基本上需要保留前驱值。 - LiranBo

一个二维数组是表示图形的一种方式，它被称为邻接矩阵。 - turingcomplete

@turingcomplete 邻接矩阵可以存储在二维数组中，但并非所有的二维数组都是邻接矩阵。s 不是 图的邻接矩阵。它甚至不是方阵。 - Phillip

@Phillip 这是正确的，但你可以将其视为一个KxK矩阵，其中K = max(M, N)，并用表示“无路径”的某个值填充新条目，以避免这种情况。 - turingcomplete

虽然那样做可以给你一个邻接矩阵，但它仍然不是与这个问题相关的那个。这个问题的邻接矩阵是一个 (m·n)×(m·n) 的矩阵，并且不包含 s 作为子矩阵。 - Phillip

你的例子中存在一个负循环。Belman-Ford算法（或其他算法）都无法解决这个问题。有可能你会在得到负无穷大的情况下一直在-8和-3分值的房间之间走动。 - ciamej

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 就是必需的），或者在生成邻居的代码片段中添加额外的行。

现在你可以 根据维基百科 实现它。你有一个图。

为什么你不应该听从？
更好的方法是使用 Belman-Ford 算法从其他顶点开始。请注意，如果你知道从 A 到 B 的最优路径，你也知道从 B 到 A 的最优路径。为什么？因为你总是要为最后一个顶点付费，而不用为第一个顶点付费，所以你可以忽略它们的成本。其余的显而易见。
现在，如果你知道你想知道路径 A->B 和 B->C，你可以使用一次从节点 B 开始的 BF 计算出 B->A 和 B->C，以及反向路径 B->A。就这样。
你只需要删除 entry 和 exit 节点的出边即可。

然而，如果你需要非常快的算法，你必须进行优化。但我认为这是另一个话题了。此外，似乎没有人对艰难的优化感兴趣。
我可以快速添加一些小而简单的优化基础，你可以忽略与相应远离的顶点的放松。在数组中，你可以轻松计算距离，因此这是一种令人愉悦的优化。
我没有提到众所周知的优化，因为我相信它们都在网络的随机过程中。

- Tacet

---

存在良好的优化（使用它，该图是平面图），但我不能保证我会有时间描述它。然而，问题是关于Bellman Ford算法的简单实现。如果没有人真正对此优化感兴趣，我将不考虑描述。 - Tacet