二维阵列中的Belman-Ford算法

Question

将Bellman-Ford算法应用于2D阵列时遇到问题(不是图形)

输入数组具有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,2]之前走过去[3,3] ].

我的问题是,在Bellman-Ford算法中实现它的最佳方法是什么？我知道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需要更多的内存,但我相信它在这里更具可读性.在你的代码中它可能不会出现.)

显然你必须有其他具有距离的2D阵列和(如果必要的话)前任,但我认为它很清楚,我不必描述它.

附加条件:
你想知道从进入退出的成本,但你必须访问一些顶点compulsory.来计算的话最简单的方法是从计算成本enter,以compulsory从compulsory到exit.(将有两个单独的计算.)它不会改变大的时间.之后,您可以添加结果.

你必须保证exit以前不可能访问compulsory.这很简单,你可以exit通过在is_correct函数中添加额外的行来删除传出的边缘(然后需要顶点v)或者生成邻居代码片段.

现在您可以基于维基百科实现它.你有图表.

为什么你不应该听？
更好的方法是从其他顶点使用Belman Ford算法.请注意,如果您知道从A到B的最佳路径,您还知道从B到A的最佳路径.为什么？总是你必须支付最后一个顶点并且你不需要先付费,所以你可以忽略它们的成本.休息很明显.
现在,如果您知道要知道路径A-> B和B-> C,则可以使用节点B的一次BF和反向路径B-> A来计算B-> A和B-> C. 结束了.
你只需要擦除出边entry和exit节点.

但是,如果您需要非常快速的算法,则必须对其进行优化.但我认为这是另一个话题.此外,似乎没有人对硬优化感兴趣.
我可以快速添加,只是那个小而简单的优化基础,你可以忽略相应的遥远顶点的放松.在数组中,您可以轻松地计算距离,因此它是令人愉快的优化.
我没有提到熟悉的优化,因为我相信所有这些都是在网络的随机过程中.