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

■実装

// 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で埋められるので勿体無いね。

優先度つきキューを使用したダイクストラ法をJavaScriptで実装した。

■実装

/**
 * Vertex
 * @param int value
 */
var Vertex = function(value){
    var self = this;
    self.value    = value;
    self.state    = 0;
    self.dist     = Number.POSITIVE_INFINITY;// もしくは十分に大きい値とか
    self.neighbor = [];
    self.appendNeighbor = function(){
        for(var i = 0; i < arguments.length; i++){
            self.neighbor.push(arguments[i]);
        }
    }
}

// set up a graph
var s  = new Vertex(0);
var v1 = new Vertex(1);
var v2 = new Vertex(2);
var v3 = new Vertex(3);
var v4 = new Vertex(4);
var g  = new Vertex(5);

// set up connections
// 単純化のためループや往路を除去した
s.appendNeighbor(
    {"weight" : 1, "vertex" : v1},
    {"weight" : 3, "vertex" : v2}
);
v1.appendNeighbor(
    {"weight" : 1, "vertex" : v2},
    {"weight" : 4, "vertex" : v3}
);
v2.appendNeighbor(
    {"weight" : 1, "vertex" : v3}
);
v3.appendNeighbor(
    {"weight" : 1, "vertex" : v4},
    {"weight" : 10, "vertex" : g}
);
v4.appendNeighbor(
    {"weight" : 1, "vertex" : g}
);
g.appendNeighbor(
);

// initialize
var vertexes = [s, v1, v2, v3, v4, g];
var pred     = [];
var pq       = new BinaryHeap();// sからの距離が短い頂点順の優先度つきキュー
s.dist = 0;
for(var i = 0; i < vertexes.length; i++){// キューの生成
    pred[i] = -1;
    pq.insert(vertexes[i], vertexes[i].dist);
}

// search
var dijkstraPQ = function(){
    while(pq.getList().length > 0){
        var u = pq.getPrior();// スタートからの距離が近い頂点を取得しcurrent頂点とする
        for(var i = 0; i < u.neighbor.length; i++){
            var neighbor  = u.neighbor[i].vertex;
            var weight    = u.neighbor[i].weight;// 隣接点の距離...(a)
            var newLength = u.dist + weight;// current頂点のsからの距離と(a)を加算...(b)
            // (b) < visitした時の距離の場合
            // キューを更新し、最短経路も更新する
            if(newLength < neighbor.dist){
                pq.changePriority(neighbor, newLength);
                neighbor.dist = newLength;
                pred[neighbor.value] = u.value;
            }
        }
    }
}
dijkstraPQ();

// 最短経路
console.log(pred);// [-1, 0, 1, 2, 3, 4]
// g<-v4<-v3-<v2<-v1<-s

// 最短距離
console.log(g.dist);// 5

任意の頂点に対して一つ前の頂点とその時の距離が分かる。

■特性

• 辺の重みは0より大きい値
• 重みの和が0より小さい閉路が存在すると無限ループする可能性がある

/**
 * BinaryHeap
 */
var BinaryHeap = function(){
    var self = this;
    self._ary  = [];
}
BinaryHeap.prototype._build = function(){
    var self = this;
    /**
     * heapify
     * 3要素を比較し最も小さい要素を親とする
     * @param {array} ary
     * @param {int} i
     * @param {max} max
     */
    var heapify = function(ary, i, max){
        /**
         * swap
         * @param {array} ary
         * @param {int} x
         * @param {int} y
         */
        var swap = function(ary, x, y){
            var a = ary[x];
            var b = ary[y];
            ary[x] = b;
            ary[y] = a;
            return true;
        }
        
        var l = 2 * i + 1;
        var r = 2 * i + 2;
        var li = 0;
        if(l < max && ary[l].priority < ary[i].priority){
            li = l;
        }
        else{
            li = i;
        }
        if(r < max && ary[r].priority < ary[li].priority){
            li = r;
        }
        if(li !== i){
            swap(ary, i, li);
            heapify(ary, li, max);
        }
    }
    var ary = self._ary;
    for(var i = ary.length - 1; i >= 0; i--){
        heapify(ary, i, self._ary.length);
    }
}
/**
 * BinaryHeap::insert
 * @param {Object} elm
 * @param {int} priority
 */
BinaryHeap.prototype.insert = function(elm, priority){
    var self = this;
    self._ary.push({
        "priority" : priority,
        "elm"      : elm
    });
    self._build();
}
/**
 * BinaryHeap::changePriority
 * @param {Object} elm
 * @param {int} priority
 */
BinaryHeap.prototype.changePriority = function(elm, priority){
    var self = this;
    var ary  = self._ary;
    for(var i = 0; i < ary.length; i++){
        if(elm === ary[i]["elm"]){
            ary[i]["priority"] = priority;
            self._build();
            return true;
        }
    }
    return false;
}
/**
 * BinaryHeap::getPrior
 */
BinaryHeap.prototype.getPrior = function(){
    var self = this;
    var elm  = self._ary.shift();
    self._build();
    return elm["elm"];
}
/**
 * BinaryHeap::getList
 */
BinaryHeap.prototype.getList = function(){
    var self = this;
    return self._ary;
}

/**
 * Vertex
 * @param int value
 */
var Vertex = function(value){
    var self = this;
    self.value    = value;
    self.state    = 0;
    self.neighbor = [];
    self.appendNeighbor = function(){
        for(var i = 0; i < arguments.length; i++){
            self.neighbor.push(arguments[i]);
        }
    }
}

// set up a graph
var s  = new Vertex(0);
var v1 = new Vertex(1);
var v2 = new Vertex(2);
var v3 = new Vertex(3);
var v4 = new Vertex(4);
var v5 = new Vertex(5);
var v6 = new Vertex(6);
var v7 = new Vertex(7);
var v8 = new Vertex(8);
var g  = new Vertex(9);
s.appendNeighbor(v1, v4);
v1.appendNeighbor(s, v2);
v2.appendNeighbor(v1, v3);
v3.appendNeighbor(v2, v4, g);
v4.appendNeighbor(v3, v5, s);
v5.appendNeighbor(v4);
v6.appendNeighbor(v7);
v7.appendNeighbor(v6);
g.appendNeighbor(v3);
var vertexes = [s, v1, v2, v3, v4, v5, v6, v7, v8, g];

// initialize
var pred       = [];
var distance   = [];
var queue = [];
var counter    = 0;
for(var i = 0; i < vertexes.length; i++){
    pred[vertexes[i].value]       = -1;
    distance[vertexes[i].value]   = -1;
}

// search
s.state = 1;
distance[s.value] = 0;
queue.push(s);
var breadthFirstSearch = function(){
    while(queue.length > 0){
        var vertex = queue.shift();// 処理する頂点
        for(var i = 0; i < vertex.neighbor.length; i++){// 隣接点全てに対して
            var n = vertex.neighbor[i];
            if(vertex.neighbor[i].state === 0){
                distance[n.value] = distance[vertex.value] + 1;// 処理中の頂点+1の距離
                pred[n.value]     = vertex.value;// 処理中の頂点の値
                n.state           = 1;// visitした記録
                queue.push(n);// 隣接点をキューに入れる
            }
        }
        vertex.state = 2;// 処理し終わった記録
    }
}
breadthFirstSearch();

// 1つ前の節点の値
console.log(pred);// [-1, 0, 1, 4, 0, 4, -1, -1, -1, 3]

// 各節点のスタートからの距離
console.log(distance);// [0, 1, 2, 2, 1, 2, -1, -1, -1, 3]

console.log(vertexes);

スタート地点から全体に探索菌が同速度で広がっていくイメージだね。

■特性

• 無向グラフでも有向グラフでも機能する
• 重みでなくステップ数での最短距離を求めることができる
• 節点をQueueに蓄えるので巨大グラフでは巨大なストレージが必要となる
• スタートから辿れない頂点は基本的には訪問しない