@blog.justoneplanet.info

■実装

グラフは以下のようにして実装した。グラフは前回のものと同様だがベルマンフォード法では負の重みも存在しうるので、経路が存在しない部分はnullとした。

// Graph //前回のグラフと同じグラフを使用
var vertexes = [
     [null, 1,    3,    null, null, null],// vertex s
     [null, null, 1,    4,    null, null],// vertex 1
     [null, null, null, 1,    null, null],// vertex 2
     [null, null, null, null, 1,    10],//   vertex 3
     [null, null, null, null, null, 1],//    vertex 4
     [null, null, null, null, null, null] // vertex g
];

// initialize
var dist    = [];
var pred    = [];
for(var i = 0; i < vertexes.length; i++){
    dist[i] = Number.POSITIVE_INFINITY;
    pred[i] = -1;
}
dist[0] = 0;// start

// 計算
(function(){
    var n = vertexes.length;
    for(var i = 1; i <= n; i++){
        // i=nの時
        // destinationと自身が同じであるにも関わらず
        // 後述のnewLenの方が短い場合、
        // 負の閉路が存在していることを示す
        failOnUpdate = (i === n);
        leaveEarly   = true;
        for(var u = 0; u < n; u++){
            for(var ci = 0; ci < n; ci++){
                if(vertexes[u][ci] === null){continue;}//経路が存在しない
                var newLen = dist[u] + vertexes[u][ci];//頂点uを経由したciへの距離
                if(newLen < dist[ci]){// 頂点u経由の方が短い場合はアップデートする
                    if(failOnUpdate){
                        throw new Error('Graph has negative cycle');
                    }
                    dist[ci] = newLen;
                    pred[ci] = u;
                    leaveEarly = false;
                }
            }
        }
        if(leaveEarly){
            break;
        }
    }
})();

// 結果表示
console.log("最短経路");
console.log(pred);// [-1, 0, 1, 2, 3, 4]
console.log("最短距離");
console.log(dist);// [0, 1, 2, 3, 4, 5]

但し、上述の場合では負の重みが存在しない。

負の重み

従って以下のデータでテストしてみる。

var vertexes = [
     [null, 1,    3,    null, null, null],// s
     [null, null, 1,    4,    null, null],// 1
     [null, null, null, 1,    null, null],// 2
     [null, null, null, null, 1,    -10],// 3
     [null, null, null, null, null, 1],// 4
     [null, null, null, null, null, null] // g
];

以下のような結果となる。

console.log("最短経路");
console.log(pred);// [-1, 0, 1, 2, 3, 3]
console.log("最短距離");
console.log(dist);// [0, 1, 2, 3, 4, -7]

3→gの距離が4を経由するよりも近くなり、s〜gの重みは-7となった。

負の閉路

以下のように閉路（ループ）で総和が負の値になるような経路を用意する。

var vertexes = [
     [null, -1,   3,    null, null, null],// s
     [null, null, -10,  4,    null, null],// 1
     [5,    null, null, 1,    null, null],// 2
     [null, null, null, null, 1,    -10],// 3
     [null, null, null, null, null, 1],// 4
     [null, null, null, null, null, null] // g
];

以下のようなエラーが発生する。

//Uncaught Error: Graph has negative cycle

ベルマンフォード法は負の重みがあった場合でも処理が可能であるが、総和が0より小さい負の閉路が存在していた場合は使用できない。但し、そのような場合は最短経路自体が意味を成さない。ちなみに密グラフには向かないアルゴリズムであるので、多次元配列（行列）でのグラフ生成は良くないかもしれない。(●´⌓`●)