gpt4 book ai didi

algorithm - Floyd-warshall 用于无向图的最长距离

转载 作者:塔克拉玛干 更新时间:2023-11-03 05:17:25 30 4
gpt4 key购买 nike

我想使用 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 [第一个节点,第二个节点,权重]

最佳答案

Floyd-Warshal 应该可以。首先请注意,当人们谈论最长距离问题及其 NP 难度时,会产生混淆。

从这里link :

notice that there is a huge confusion when we talk about the longest path:

The longest path problem commonly means finding the longest simple path. The shortest path problem, however, focuses on finding the shortest (simple or non-simple) path.

如果原始图 G 没有正循环,则 -G,即通过取反 G 的边创建的图,将没有负边,并且您可以使用 Floyd-Warshall 找到 -G 中的最短路径,从而找到 G 中的最长路径。因此,如果您的输入图没有正循环,Floyd-Warshall 应该可以工作。另见 here .

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

关于algorithm - Floyd-warshall 用于无向图的最长距离,我们在Stack Overflow上找到一个类似的问题: https://stackoverflow.com/questions/42500120/

30 4 0
Copyright 2021 - 2024 cfsdn All Rights Reserved 蜀ICP备2022000587号
广告合作:1813099741@qq.com 6ren.com