■実装
以下のように実装した。
//Graph var vertexes = [ [null, 2, null, null, 4],// vertex 1 [null, null, 3, null, null],// vertex 2 [null, null, null, 5, 1],// vertex 3 [8, null, null, null, null],// vertex 4 [null, null, null, 4, null]// vertex 5 ]; // initialize var dist = []; var pred = []; var n = vertexes.length; for(var u = 0; u < n; u++){ dist[u] = []; pred[u] = []; for(var i = 0; i < n; i++){ dist[u][i] = Number.POSITIVE_INFINITY;// 経路が存在しない場合は無限 pred[u][i] = -1; if(vertexes[u][i] !== null){ dist[u][i] = vertexes[u][i];// 元グラフの経路を代入 pred[u][i] = u; } } dist[u][u] = 0;// 自身に対しては0の距離が存在する } console.log('dist:'); console.log(dist);//...(a) // 計算 for(var k = 0; k < n; k++){ for(var i = 0; i < n; i++){ if(dist[i][k] === Number.POSITIVE_INFINITY){ continue; } // 任意の頂点まで有限の距離が開いているとき // 有限距離 を経由した任意の頂点を選択し // そこまでの距離が既に計算したものよりも小さい場合に // その値で上書きする for(var j = 0; j < n; j++){ var newLength = dist[i][k];// ik newLength += dist[k][j]; if(newLength < dist[i][j]){ dist[i][j] = newLength; pred[i][j] = pred[k][j]; } } } } // 結果 console.log("dist:"); console.log(dist);//...(b)
(a)の時、distは以下のようになる。
0 | 2 | Infinity | Infinity | 4 |
Infinity | 0 | 3 | Infinity | Infinity |
Infinity | Infinity | 0 | 5 | 1 |
8 | Infinity | Infinity | 0 | Infinity |
Infinity | Infinity | Infinity | 4 | 0 |
殆ど元グラフと変わらない。結果(b)は、以下のようになる。
0 | 2 | 5 | 8 | 4 |
16 | 0 | 3 | 8 | 4 |
13 | 15 | 0 | 5 | 1 |
8 | 10 | 13 | 0 | 12 |
12 | 14 | 17 | 4 | 0 |
例えば0→1は距離が2、0→2は距離が5、0→3は距離が8、0→4は距離が4であり、1→0は距離が16である。
経路
終了時のpredは以下のようになる。
-1 | 0 | 1 | 4 | 0 |
3 | -1 | 1 | 2 | 2 |
3 | 0 | -1 | 2 | 2 |
3 | 0 | 1 | -1 | 0 |
3 | 0 | 1 | 4 | -1 |
例えば0→1の一つ前の頂点は始点0、0→2の一つ前の頂点は頂点1、0→3の一つ前の頂点は頂点4、0→4の一つ前の頂点は0であり、1→0の場合は頂点3が終点の一つ前である。
■おまけ
ちなみに表は以下のようにして描画した。
document.write('<table border="1" cellpadding="0" cellspacing="0">'); dist.forEach(function(e1, i1, ary1){ document.write('<tr>'); e1.forEach(function(e2, i2, ary2){ document.write('<td>' + e2 + '</td>'); }); document.write('</tr>'); }); document.write('</table>');
そろそろJavaScriptでもforEachを使って良い頃だと思う。