prog*sig

SVGで最短経路表示の勉強 - jsdo.it - Share JavaScript, HTML5 and CSSのデータ部分を借りて、それの最短経路を探索するJavaScriptを書いた。
ダイクストラ法（最短経路問題）を参考にした。


こんな感じで

(function() {
    var startNode = data["A"];
    var endNode = data["F"];
    var queue = [];
    // キューに追加する
    var pushQueue = function(node) {
        if (!_.include(queue, node)) {
            queue.push(node);
        }
    }
    var popQueue = function() {
        var key = "minCost";
        // キューに入れられたNodeはminCostを持っている
        if (queue.length > 1) {
            // 大きい順に並び替える - 降順
            queue.sort(function (b1, b2) {
                return b1[key] > b2[key] ? -1 : 1;
            });
        }
        return queue.pop();
    }
    // nextNodeのdataを配列にしたものを返す
    var analyzeNearnodeCost = function(node) {
        // そのノードからいけるノードデータ集合
        var edgeList = node["edgeList"];
        _.each(edgeList, function(ele, index, array) {
            if (!ele) { // IEで何故か回ってくる時があるため回避
                return;
            }
            var nextNode = ele.nextNode;
            var currentNode = data[nextNode];
            // cost = 確定ノードまでのコスト＋エッジのコスト
            var cost = node.minCost + ele.weight;
            // 現在地と来る場所のminCostから、現在地のminCostを決定する。
            setMinCost(currentNode, node, cost);
        });
    }
    var setMinCost = function(currentNode, fromNode, cost) {
        var currentWeight = currentNode.weight;
        // ノードの現在値よりも小さければ更新
        if (currentNode.minCost < 0 || currentNode.minCost > cost) {
            currentNode.minCost = cost;
            // 「どこから来たのか」を記録する
            currentNode.from = fromNode.id;
            // キューに追加する
            pushQueue(currentNode);
        }
    }
    var main = function(startNode) {
        // 初期化：スタートノードの値(最小コスト候補)を0，他のノードの値を未定義（または∞,今回は-1）に設定。
        // また最初は全部確定してないので、data[nodeid].done = false;にする
        for (var nodeid in data) {
            data[nodeid].minCost = -1;
            data[nodeid].done = false;
        }
        startNode.minCost = 0;// 自分自身のコストは0
        queue.push(startNode);
        var doneNode = null // 確定ノード
        // 確定ノードをピックアップすることができなくなるまで（＝変化がなくなるまで）以下のループを繰り返す：
        while (!_.isEmpty(queue)) {
            // 優先度が高い(=minCostが最小の)確定ノードを取り出す
            doneNode = popQueue();
            console.log(doneNode.id);
            // 確定フラグを立てる
            doneNode.done = true;
            analyzeNearnodeCost(doneNode);
        }
    }
    var getResultDijkstra = function() {
        var result = [];
        result.unshift(endNode.id);// startNode -> ... -> endNode とする
        // 後ろからfromを辿っていく
        var resultLine = function line(node) {
            if (node.from) {
                result.unshift(node.from);
                line(data[node.from]);
            }
        }
        resultLine(endNode);
        return result;
    }
    main(startNode);
    // window
    window.getResultDijkstra = getResultDijkstra;
})();

どういう仕組みかというのはほぼダイクストラ法（最短経路問題）の優先度付き待ち行列的な実装のままなので、そちらの解説を読むのがいい。

ダイクストラ法はDP（動的計画法）的なアルゴリズムです。 つまり，「手近で明らかなことから順次確定していき，その確定した情報をもとにさらに遠くまで確定していく」方法で， DPと同じ精神を持っています。

ダイクストラ法（最短経路問題）

ということなので、手近=ノードAから一番近いノード(=C)から調べて確定、次にノードCから手近なノードを調べてを繰り返しみたいな感じです。
一番近いノードというのは今回優先度キューで表すところですが、適当に書いたので、キューをminCostでソートして、一番minCostが小さいものを優先的に使うという感じにしました。

// 優先度が高い(=minCostが最小の)確定ノードを取り出す
doneNode = popQueue();

優先度を使ってキューを取り出すという所を、下のように適当に取り出した場合も何故か上手く行くようです。

// 単純に後ろから取り出す
doneNode = queue.pop();

しかし、両方のやり方を比べてみると、やっぱり優先度を使わないと無駄な走査が起きる。(まあ、それも何とかしようと思えばできると思いますが、アルゴリズム的な意味合いで無駄が少ない)
// 単純に後ろから取り出す(何回も同じものをキューに入れてる)
A -> D -> E -> F -> C -> D -> E -> F -> B
// 優先度キューを使い取り出す(pushQueueで重複チェックがあるので、同じものは連続して入らない)
A -> C -> D -> E -> B -> F

確実にもっとましな実装はできそうな内容だけど…