algorithm - 矩阵中的最大路径成本

Question

谁能告诉我在 NxM 矩阵中找到最大路径成本的算法，该矩阵从左上角开始到右下角结束，矩阵中允许向左、向右、向下移动并包含负成本。一个单元格可以被访问任意次数，并且在访问一个单元格之后，它的成本被替换为 0

约束
1 <= nxm <= 4x10^6
输入

4 5
1 2 3 -1 -2
-5 -8 -1 2 -150
1 2 3 -250 100
1 1 1 1 20

输出

37

图片中给出了解释 Explanation of Output

Answer 1

因为你也有负成本，所以使用 bellman-ford。您要做的是更改所有成本的符号(将负号转换为正号，将正号转换为负号)，然后找到最短路径，而这条路径将是最长的，因为您已更改符号。

如果符号永远不会变为负数，则使用 dijkstra shrtest-path 但在此之前使所有值都为负数，这将返回最长的路径及其成本。

你的矩阵是一个有向图。在您的图像中，您试图找到从索引 (0,0) 到 (n-1,n-1) 的路径(最大或最小)。

您需要这些东西来将其表示为图表。

• 你需要一个链表并且在每个节点中你有一个first_Node, second_Node,Cost to move from first node to second .
• 一个链表数组。在每个数组索引中，您保存一个链表。例如，如果有一条从 0 到 5 和 0 到 1 的路径(这是一个无向图)，那么您的图将如下所示。

如果你想要一个有向图，那么只需添加 adj[0] = 5 而不要添加 adj[5] = 0 ，这意味着存在从 0 到 5 而不是从 5 到 0 的路径。

这里的链表只表示没有成本连接的节点。你必须在那里添加额外的变量来保持每两个节点的成本，它看起来像这样。

现在不用第一个链表，而是将这个链表放入您的数组中，您现在就有了一个图来运行最短或最长路径算法。

如果你想要一个智能算法，那么你可以使用带启发式的 A*，我想曼哈顿会是最好的。

如果边的成本不是负数，则使用 Dijkstra。

如果成本为负，则使用 bellman-ford 算法。

您总是可以通过将减号转换为加号并将加号转换为减号然后运行最短路径算法来找到最长路径。建立的路径将是最长的。

我回答了这个问题，正如您在评论中所说，要看第二点。如果这是一项任务，那么这项任务的主要思想是确保 Monotonocity .

• h 代表启发式成本。
• A 代表累计成本。

这表示每个节点 h(A) =< h(A) + A(A,B) .意味着如果你想从 A 移动至 B那么成本不应该减少(你可以用你的值做一些事情来保持这个属性)但是增加并且一旦你满足这个条件然后每个节点 A * 选择，那个节点将成为你从源到目标的路径的一部分因为这是具有最短/最长值的路径。

pathMax 您可以强制执行单调性。如果有来自 A 的路径至 B这样 f(S...AB) < f(S...B) 然后设置 f(S...AB) 的成本 = Max(f(S...AB) , f(S...A )) 其中 S 表示来源。