@blog.justoneplanet.info

前回の記事では、生成するグラフが疎であったので連結リストを使用した。密グラフ向けに行列でも実装した。

■実装

// Graph //（密ではないが）前回のグラフと同じグラフを使用
var Vertexes = [
             [0, 1, 3, 0, 0, 0],// s
             [0, 0, 1, 4, 0, 0],// 1
             [0, 0, 0, 1, 0, 0],// 2
             [0, 0, 0, 0, 1,10],// 3
             [0, 0, 0, 0, 0, 1],// 4
             [0, 0, 0, 0, 0, 0] // g
];

// initialize
var dist    = [];
var pred    = [];
var visited = [];
for(var i = 0; i < Vertexes.length; i++){
    dist[i] = Number.POSITIVE_INFINITY;
    pred[i] = -1;
    visited[i] = false;// 訪問を記録する
}
dist[0] = 0;// start

// search
var dijkstraMX = function(){
    var getMin = function(){
        var tmp = Number.POSITIVE_INFINITY;
        for(var i = 0; i < Vertexes.length; i++){
            if(visited[i] === false && dist[i] < tmp){
                tmp = i;
            }
        }
        if(tmp === Number.POSITIVE_INFINITY){
            tmp = null;
        }
        return tmp;
    }

    while(true){
        var u = getMin();// 未訪問の中でスタートから最小の距離の頂点
        // 「sから辿れない頂点しか残っていない場合」「未訪問が無い場合」はループ終了
        if(dist[u] === Number.POSITIVE_INFINITY || u === null){break;}
        visited[u] = true;
        for(var i = 0; i < Vertexes[u].length; i++){
            if(Vertexes[u][i] > 0){// 辺が存在している
                var neighbor  = i;//隣接点(a)
                var weight    = Vertexes[u][i];// (a)との辺の重み
                var newLength = dist[u] + weight;// (b)
                // 現在セットされている、スタート地点から隣接点までの距離が
                // 新しい経路での値より大きい時
                if(newLength < dist[neighbor]){
                    dist[neighbor] = newLength;
                    pred[neighbor] = u;
                }
            }
        }
    }
}
dijkstraMX();

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

// 最短距離
console.log(dist);// [0, 1, 2, 3, 4, 5]

グラフが疎である場合、行列を使用すると殆どの空間が0で埋められるので勿体無いね。