使用Floyd算法找到最短路径

Question

使用Floyd算法找到最短路径

c++algorithmgraphshortest-pathfloyd-warshall

3

我有一个邻接矩阵，其中包含许多0和1。如果一个节点之间没有边，则该字段为0，否则该字段标记为1。

然后，如果邻接矩阵中的一个字段为0，则节点之间没有边，否则存在一条权重为1的边。

现在，我已经应用了Floyd算法来找出从任何一个节点到其他每个节点的最短路径。但是我得不到正确的解决方案。

以下是我的Floyd算法实现。

void Floyd_Warshal(int graph[Nodes][Nodes], int D[Nodes][Nodes])
{
    for (int i = 0; i < Nodes; i++)
    {
        for (int j = 0; j < Nodes; j++)
        {
            if (graph[i][j] == 0) { graph[i][j] = INT_MAX; }
            D[i][j] = graph[i][j];
        }
    }
    for (int k = 0; k < Nodes; k++) {
        for (int i = 0; i < Nodes; i++)
        {
            for (int j = 0; j < Nodes; j++)
            {
                if (D[i][j] > D[i][k] + D[k][j]) {
                    D[i][j] = D[i][k] + D[k][j];
                }
            }
        }
    }
}

我已将0设置为INT_MAX，以便构建算法的标准矩阵，但我没有得到正确的解决方案。

此外，这是我的矩阵示例：

将矩阵应用于算法后，矩阵中的任何0都将转换为INT_MAX。我希望得到的权重是2或1，但我却得到了意外的值，如-2712323...

- VCL_D

1

你能同时附上一个邻接矩阵的例子吗？ - ralzaul

请说明您期望的输出和实际输出有何不同。另外，您能否澄清一下“如果从特定节点到任何其他节点都没有边，则该字段将为0，否则该字段将标记为1”的含义。 - Petr

@ralzaul 我已更新帖子以添加示例。 - VCL_D

@Petr 我的意思是，例如如果节点A到节点C之间没有任何边，那么矩阵中A-C的值将为0，否则该值将为1。 - VCL_D

1

@VCL_D，我稍微修改了你的问题，以使其更清晰，因为当你说“任何其他节点”时，这似乎意味着你指的是所有其他节点，而不仅仅是与邻接矩阵中该元素对应的特定其他节点。 - Petr

@Petr 谢谢你的帮助 :) - VCL_D

1个回答

网页内容由stack overflow 提供, 点击上面的

可以查看英文原文，
原文链接

- Petr · Accepted Answer

你得到非常大的负值的原因是整数溢出。

如果没有边缘，你就将 D[i][j]=INT_MAX。但是，接着

            if (D[i][j] > D[i][k] + D[k][j]) {
                D[i][j] = D[i][k] + D[k][j];

如果从i到k和从k到j没有边，则总和将溢出并且结果将为负数。之后，您的算法将认为存在一条非常短（大负数）的路径从这个i到这个j，这将毒害所有其他路径。

我建议您使用INT_MAX / 2而不是INT_MAX。