3

我有一个包含数字 0 和 1 的邻接矩阵。如果从一个节点到另一个节点没有边，则该字段将为 0，否则该字段将标记为 1。

那么，如果邻接矩阵中的某个字段为0，则节点之间不存在边，否则存在权重为1的边。

现在，我已经应用 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，以便为算法构建标准矩阵，但我没有得到正确的解决方案。

另外，这是我的矩阵的一个例子：

  A B C D
A 0 0 1 0
B 1 1 0 1
C 0 0 1 0
D 1 0 0 0

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

4

1 回答 1

5

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

如果没有边缘，则设置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如果从tok和 from kto没有边j，则和将溢出，结果将为负数。之后，您的算法会认为从 thisi到 this有一条非常短（大的负数）路径j，这将毒害所有其他路径。

我建议你INT_MAX/2改用 if INT_MAX。

于 2015-06-25T14:46:11.170 回答