弗洛伊德-沃尔算法-表示“无穷大”

Question

使用弗洛伊德-沃尔的算法寻找两个顶点之间的最短路径，在Java中实现时，我应该如何表示无穷大？我用无穷大来表示两个顶点之间没有路径。

谢谢

Answer 1

答案取决于用来表示权重的数据类型。如果是double，那么使用Double.POSITIVE_INFINITY是安全的。如果它是整数，选择一个不使用的值，例如，如果图形不允许负边，则选择负值。

这样做的一个不幸后果是，您需要注意三个循环中的无穷大元素:与其使用“直”加法，还需要检查它是否是特殊的“无穷”值，然后才进行添加：

final int INFINITY = -1;
...
for (int k = 0 ; k != N ; k++) {
    for (int i = 0 ; i != N ; i++) {
        for (int j = 0 ; j != N ; j++) {
            if (g[i][k] == INFINITY || g[k][j] == INFINITY) continue;
            int total = g[i][k] + g[k][j];
            if (g[i][j] != INFINITY) {
                g[i][j] = Math.min(g[i][j], total);
            } else {
                g[i][j] = total;
            }
        }
    }
}

Answer 2

如果使用Integer/Long或Float/Double而不是int/long或float/double，则可以使用null值来表示无穷大。