寻找无向加权图的最重路径（最大权重和）？贝尔曼福特——

Question

有一个矩阵，它的每个单元格都包含一个整数值（包括正数和负数）。你在矩阵中得到了一个初始位置，现在你必须找到一条路径，使你穿过的所有单元格的总和最大。您可以上、下、右、左移动，并且只能穿过一个单元格一次。
我的解决方案是使用 Bellman Ford 算法：让我们用相反的数字替换所有值，现在我们得到了一个新矩阵。然后，我从新矩阵创建一个无向图，每个单元格都是一个节点，踩在一个单元格上会消耗该单元格的值 - 即权重。所以，我只需要使用 Bellman-Ford 算法找到图形的最短路径。该路径将是我们初始矩阵的最长路径。好吧，有一个问题。该图包含负环，也有太多的节点和边。因此，结果不正确。
这是我的代码：

知道xd和yd是机器人的初始坐标

void MatrixToEdgelist()
{
    int k = 0;
    for (int i=1;i<=n;i++)
        for (int j=1;j<=n;j++)
    {
        int x = (i - 1) * n + j;
        int y = x + 1;
        int z = x + n;
        if (j<n)
        {
            edges.push_back(make_tuple(x, y, a[i][j+1]));
        }
        if (i<n)
        {
            edges.push_back(make_tuple(x, z, a[i+1][j]));
        }
    }
}

   void BellmanFord(Robot r){
        int x = r.getXd();
        int y = r.getYd();
        int z = (x-1)*n + y;
        int l = n*n;
        int distance[100];
        int previous[100]{};
        int trace[100];
    
        trace[1] = z;
        for (int i = 1; i <= l; i++) {
            distance[i] = INF;
        }
    
        distance[z] = a[x][y];
        for (int i = 1; i <= l-1; i++) {
            for (auto e : edges) {
                int a, b, w;
                tie(a, b, w) = e;
                //distance[b] = min(distance[b], distance[a]+w);
                if (distance[b] < distance[a] + w)// && previous[a] != b)
                {
                    distance[b] = distance[a] + w;
                    previous[b] = a;
                }
            }
    
        }
    
        //print result
        int Max=INF;
        int node;
        for (int i=2;i<=l;i++)
        {
            if (Max < distance[i])
            {
                Max = distance[i];
                node = i;
            }
        }
    
        if (Max<0)cout << Max << "\n";
        else cout << Max << "\n";
        vector<int> ans;
        int i = node;
        ans.push_back(i);
        while (i != z)
        {
            i = previous[i];
            ans.push_back(i);
        }
    
        for (int i=ans.size()-1;i>=0;i--)
        {
            int x, y;
            if (ans[i] % n == 0)
            {
                x = ans[i] / n;
                y = n;
            }
            else{
                x = ans[i] / n + 1;
                y = ans[i] - (( x - 1 ) * n);
            }
            cout << x << " " << y << "\n";
        }
    }

Example matrix

The result

显然距离应该继续更新，但它没有。它停在最后一个节点。

Answer 1

“让我们用相反的数字替换所有值”

不确定你所说的相反数字是什么意思。无论如何，这是不正确的。

如果您有负权重，那么通常的解决方案是将最负权重的绝对值添加到每个权重。

为什么Bellman-Ford？ Dijkstra 应该足以解决这个问题。（默认情况下，Dijkstra 会找到最便宜的路径。您可以通过将（原始权重减去最大权重）的绝对值分配给每个 link 来找到最昂贵的路径。）

寻找无向加权图的最重路径（最大权重和）？贝尔曼福特——

Finding heaviest path (biggest sum of weights) of an undirected weighted graph? Bellman Ford --

c++

graph

path

weighted

bellman-ford