■実装
グラフは以下のようにして実装した。グラフは前回のものと同様だがベルマンフォード法では負の重みも存在しうるので、経路が存在しない部分は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より小さい負の閉路が存在していた場合は使用できない。但し、そのような場合は最短経路自体が意味を成さない。ちなみに密グラフには向かないアルゴリズムであるので、多次元配列(行列)でのグラフ生成は良くないかもしれない。(●´⌓`●)