2

我对此有一些问题。首先，我使用 Floyd-warshall 在有向图上显示所有最小周期并且它有效，但后来我尝试将它与无向图一起使用，但它不像我需要的那样工作。

例如，假设我有这个图表：

INF     INF     19      14      8
INF     INF     13      INF     9
19      13      INF     INF     3
14      INF     INF     INF     10
8       9       3       10      INF

这应该看起来像这样：

图形表示

无论如何，由于您可以将无向图表示为有向图（就像我在示例矩阵中所做的那样），Floyd Warshall 应该可以工作，但结果不是我所期望的。使用相同的图形示例，这是具有最小路径成本的矩阵：

最小路径成本：

16      17      11      14      8
17      18      12      19      9
11      12      6       13      3
14      19      13      20      10
8       9       3       10      6

这是带有路径的矩阵：

 (0 4 0) (0 4 1) (0 4 2) (0 3)   (0 4)
 (1 4 0) (1 4 1) (1 4 2) (1 4 3) (1 4)
 (2 4 0) (2 4 1) (2 4 2) (2 4 3) (2 4)
 (3 0)   (3 4 1) (3 4 2) (3 4 3) (3 4)
 (4 0)   (4 1)   (4 2)   (4 3)   (4 2 4)

因为我只对循环感兴趣，所以我只需要矩阵的对角线。

无论如何，让我们取 0 - > 0：结果是 (0 4 0)，成本是 16

无论如何，因为我正在寻找最小周期，所以我期望类似：

0 -> 0, Path (0 4 2 0) （或 0 2 4 0 因为是无向图，但我只需要其中一个），成本为 30。

这实际上是 floyd-warshall 代码：

for (k = 0; k < V; k++)
{
    for (i = 0; i < V; i++)
    {
        for (j = 0; j < V; j++)
        {
            if (dist[i][k] != INF && dist[k][j] != INF &&
                dist[i][k] + dist[k][j] < dist[i][j]) {

                dist[j][i] = dist[i][j] = dist[i][k] + dist[k][j];
                path[i][j] = path[j][i] = path[k][j];
            }
        }
    }
}

我真的不知道我需要改变什么才能得到正确的结果（或者这可能是正确的结果，我认为不是）。

4

0 回答 0