@blog.justoneplanet.info

■実装

以下のように実装した。

//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は以下のようになる。

殆ど元グラフと変わらない。結果(b)は、以下のようになる。

例えば0→1は距離が2、0→2は距離が5、0→3は距離が8、0→4は距離が4であり、1→0は距離が16である。

経路

終了時のpredは以下のようになる。

例えば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を使って良い頃だと思う。