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

Question

1. 有一个矩阵，其每个单元格都包含一个整数值（正和负值）。您可以在矩阵中获得初始位置，现在您必须找到一条路径，即您越过所有单元格是最大的。您可以向上，向下，右，左，只有一次越过单元。
2. 我的解决方案是使用Bellman Ford算法：让我们用相反的数字替换所有值，现在我们刚刚有了一个新的矩阵。然后，我从新矩阵中创建一个无向图，每个单元格是一个节点，踏上了单元格的值的单元格成本 - 这是重量。因此，我只需要使用Bellman-Ford算法找到图形的最短路径即可。该路径将是我们初始矩阵的最长路径。 好吧，有一个问题。该图包含负周期，也有太多的节点和边缘。因此，结果不正确。
3. 这是我的代码：

知道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

结果

清楚地表明距离应该继续更新，但事实并非如此。它停在最后一个节点。

Answer 1

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

不确定您的含义是相反的数字。无论如何，这是不正确的。

如果您的重量负重，则通常的解决方案是将最负重量的绝对值添加到每个重量中。

为什么要贝尔曼福特？ Dijkstra应该足以解决这个问题。 （默认情况下，Dijkstra找到了最便宜的路径。您通过将（原始重量减去最大的最大值）的绝对值（原始重量减去最大）找到最昂贵的路径。）