5

2 つの頂点間の最短経路を見つけるために Floyd-Warshall のアルゴリズムを使用して、Java で実装するときに無限をどのように表現すればよいですか? ここで無限を使用して、2 つの頂点間にパスがないことを示しています。

ありがとう

4

2 に答える 2

5

答えは、重みを表すために使用するデータ型によって異なります。そうであればdouble、安全に使用できますDouble.POSITIVE_INFINITY。整数の場合は、使用しない値を選択します。たとえば、グラフで負のエッジが許可されていない場合は負の値を選択します。

これの残念な結果は、3 つのループ内の無限要素に注意を払う必要があるということです。「単純な」加算を使用するのではなく、それが特別な「無限」値であるかどうかを確認してから、添加：

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;
            }
        }
    }
}
于 2014-05-10T21:48:39.297 に答える
1

/または/を使用し、 Integer/LongまたはFloat/を使用Doubleしない場合、値で無限を表すことができます。intlongfloatdoublenull

于 2014-05-10T21:48:32.090 に答える