1

我想使用 Floyd-warshall 算法找到加权无向图的任意两个顶点之间的最大距离。为此，我做了一些更改：

  1. 我添加负权重而不是正数。

  2. 然后我找出最短路径。

但它没有给我正确的输出。有人可以指出我正在犯的错误。

class TestClass {
    public static void main(String args[] ) throws Exception {
        Scanner sc = new Scanner(System.in);
        int testcases=sc.nextInt();
        for(int t=0;t<testcases;t++)
        {
            int nodes=sc.nextInt();
            int edges=sc.nextInt();
            int[][] dist_mat=new int[nodes][nodes];
            for(int i=0;i<nodes;i++)
            {
                for(int j=0;j<nodes;j++)
                {
                    if(i!=j)
                    {
                        dist_mat[i][j]=Integer.MAX_VALUE;
                    }
                }
            }
            for(int i=0;i<edges;i++)
            {
                int source=sc.nextInt();
                int dest=sc.nextInt();
                dist_mat[source-1][dest-1]=-sc.nextInt();
                dist_mat[dest-1][source-1]=dist_mat[source-1][dest-1];
            }

            for(int k=0;k<nodes;k++)
            {
                for(int i=0;i<nodes;i++)
                {
                    for(int j=0;j<nodes;j++)
                    {

                        if(i!=j && j!=k && i!=k && dist_mat[i][j]>dist_mat[i][k]+dist_mat[k][j])
                        {
                            if(dist_mat[i][k]<Integer.MAX_VALUE && dist_mat[k][j]<Integer.MAX_VALUE)
                                    dist_mat[i][j]=Integer.min(dist_mat[i][j],dist_mat[i][k]+dist_mat[k][j]);
                            if(dist_mat[j][k]<Integer.MAX_VALUE && dist_mat[k][i]<Integer.MAX_VALUE)
                                    dist_mat[j][i]=Integer.min(dist_mat[j][i],dist_mat[j][k]+dist_mat[k][i]);
                        }

                    }
                }
            }   
        }
    }

相同的输入是：-

1[测试用例数]

5 4 [节点数，边数]

1 2 4 [第一个节点，第二个节点，权重]

3 2 3 [第一个节点，第二个节点，权重]

2 5 2 [第一个节点，第二个节点，权重]

4 1 1 [第一个节点，第二个节点，权重]

4

2 回答 2

2

Floyd-Warshal 应该可以工作。首先请注意，当人们谈论最长距离问题及其 NP-hardness 时存在混淆。

从这个链接：

请注意，当我们谈论最长路径时存在巨大的混淆：

最长路径问题通常意味着找到最长的简单 路径。然而，最短路径问题侧重于寻找最短（简单或非简单）路径。

如果原始图G没有正循环，则-G由 G 通过否定其边创建的图将没有负边，您可以使用 Floyd-Warshall 找到 中的最短路径-G，从而找到 中的最长路径G。因此，如果您的输入图没有正循环，Floyd-Warshall 应该可以工作。也见这里。

您的代码的一个可能问题是您将所有距离初始化为 MAX 值：dist_mat[i][j]=Integer.MAX_VALUE，而我认为在 Floyd-Warshall 中您应该将它们初始化为图形的边权重。

于 2018-11-22T18:56:19.787 回答
0

能够找到任意两个节点之间的最长路径的算法可用于确定哈密顿路径问题。然而，哈密顿路径问题是NP 完全的。Floyd-Warshall 算法产生多项式运行时界限，因此修改不太可能导致确定最长路径的算法。

于 2017-02-28T08:17:33.310 回答