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