Floyd-Warshall Algorithm - Representing "infinity"

Question

Using Floyd-Warshall's algorithm for finding the shortest path between two vertices, how should I represent infinity when implementing in Java? I'm using infinity here to say there is no path between two vertices.

Thanks

Answer 1

The answer depends on the data type that you use to represent the weight. If it is double, you would be safe to use Double.POSITIVE_INFINITY. If it is an integer, pick a value that you do not use, e.g. negative one if your graph does not allow negative edges.

An unfortunate consequence of this is that you would need to pay attention to the infinity element inside the three loops: rather than using the "straight" addition, you would need to check if it's the special "infinity" value, and only then do the addition:

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

If you use Integer/Long or Float/Double and not int/long or float/double, then you can you the null value to represent infinity.