[アルゴリズム] ダイクストラ法をやってみる ref: http://qiita.com/edo_m18/items/0588d290a19f2afc0a84

file0.js

// ノード（経路の中継点）とそのノードを生成する
var nodes = createNodes();

// ノードの開始点のコストを0にする。（スタート地点は任意）
nodes[0].cost = 0;

// 経路が見つかるまでループする
while (true) {

    // 現在処理中のノードを格納（これが見つからなければ終了）
    var processNode = null;

    // 全ノードに対して確認／アップデートを行う
    for (var i = 0; i < nodes.length; i++) {
        var node = nodes[i];

        // 訪問済み or まだコストが未設定の場合はスキップ
        // 結果として最初はスタートノードだけがコスト `0` になっているため、
        // スタートノードが選択される。
        if (node.done || node.cost < 0) {
            continue;
        }

        // 処理中ノードがなければ現在のノードを保持して次へ
        if (!processNode) {
            processNode = node;
            continue;
        }

        // 訪問済み（確定済み）でないノードのうち、一番小さいコストのノードを探す
        if (node.cost < processNode.cost) {
            processNode = node;
        }
    }

    // 処理中のノードがなくなったら、つまりすべてチェックが終わったらループ終了
    if (!processNode) {
        break;
    }

    // 処理中ノードに「訪問済み」のフラグを設定する
    // （未確定ノードのうち、一番コストが小さい場合はそこにいたるまでの経路が計算された結果なので「確定」できる
    processNode.done = true;

    // コストのアップデート
    // 選択されたノード（processNode）の現在のコストと、
    // 接続されているエッジのコストを足し、それを接続先のノードに設定されているコストと比較し、
    // もしそれよりも小さければその値にアップデートする
    for (var i = 0; i < processNode.edgesTo.length; i++) {
        var node = processNode.edgesTo[i];
        var cost = processNode.cost + processNode.edgesCost[i];

        // コストが未設定 or コストの少ない経路がある場合はアップデート
        var needsUpdate = (node.cost < 0) || (node.cost > cost);
        if (needsUpdate) {
            node.cost = cost;
            node.previousNode = processNode;
        }
    }
}

// 上記で経路が検索済みとなる

// ここでは最後のノードをゴールとしているが
// 選択するノードを変更すればそのノードまでの最短経路が算出できる
var goalNode = nodes[5];

console.log('=====================');
var path = 'Goal -> ';
var currentNode = goalNode;
while(true) {
    var nextNode = currentNode.previousNode;
    if (!nextNode) {
        path += ' Start';
        break;
    }
    path += nextNode.id + ' -> ';
    currentNode = nextNode;
}

console.log(path);
console.log('=====================');

file1.js

function Node(id) {
    this.edgesTo      = [];
    this.edgesCost    = [];
    this.done         = false;
    this.cost         = -1;
    this.id           = id;
    this.previousNode = null;
}
Node.prototype.addNode = function (node, cost) {
    this.edgesTo.push(node);
    this.edgesCost.push(cost);
};

file2.js

function createNodes() {
    var node1 = new Node(1); // start
    var node2 = new Node(2); // top
    var node3 = new Node(3); // center
    var node4 = new Node(4); // bottom-left
    var node5 = new Node(5); // bottom-right
    var node6 = new Node(6); // goal

    node1.addNode(node2, 5);
    node1.addNode(node3, 4);
    node1.addNode(node4, 2);

    node2.addNode(node1, 5);
    node2.addNode(node6, 6);
    node2.addNode(node3, 2);

    node3.addNode(node2, 2);
    node3.addNode(node1, 4);
    node3.addNode(node4, 3);
    node3.addNode(node5, 2);

    node4.addNode(node1, 2);
    node4.addNode(node3, 3);
    node4.addNode(node5, 6);

    node5.addNode(node4, 6);
    node5.addNode(node3, 2);
    node5.addNode(node6, 4);

    node6.addNode(node2, 6);
    node6.addNode(node5, 4);

    return [
        node1, node2, node3, node4, node5, node6
    ];
}

file3.js

/**
 * ノード
 */
function Node(id) {
    this.edgesTo      = [];
    this.edgesCost    = [];
    this.done         = false;
    this.cost         = -1;
    this.id           = id;
    this.previousNode = null;
}
Node.prototype.addNode = function (node, cost) {
    this.edgesTo.push(node);
    this.edgesCost.push(cost);
};

function createNodes() {
    var node1 = new Node(1); // start
    var node2 = new Node(2); // top
    var node3 = new Node(3); // center
    var node4 = new Node(4); // bottom-left
    var node5 = new Node(5); // bottom-right
    var node6 = new Node(6); // goal

    node1.addNode(node2, 5);
    node1.addNode(node3, 4);
    node1.addNode(node4, 2);

    node2.addNode(node1, 5);
    node2.addNode(node6, 6);
    node2.addNode(node3, 2);

    node3.addNode(node2, 2);
    node3.addNode(node1, 4);
    node3.addNode(node4, 3);
    node3.addNode(node5, 2);

    node4.addNode(node1, 2);
    node4.addNode(node3, 3);
    node4.addNode(node5, 6);

    node5.addNode(node4, 6);
    node5.addNode(node3, 2);
    node5.addNode(node6, 4);

    node6.addNode(node2, 6);
    node6.addNode(node5, 4);

    return [
        node1, node2, node3, node4, node5, node6
    ];
}


function main() {

    var nodes = createNodes();

    // start node is first node
    nodes[0].cost = 0;

    while (true) {
        var processNode = null;

        for (var i = 0; i < nodes.length; i++) {
            var node = nodes[i];

            // 訪問済み or まだコストが未設定
            if (node.done || node.cost < 0) {
                continue;
            }

            if (!processNode) {
                processNode = node;
                continue;
            }

            // 一番小さいコストのノードを探す
            if (node.cost < processNode.cost) {
                processNode = node;
            }
        }

        if (!processNode) {
            break;
        }

        processNode.done = true;

        for (var i = 0; i < processNode.edgesTo.length; i++) {
            var node = processNode.edgesTo[i];
            var cost = processNode.cost + processNode.edgesCost[i];

            // コストが未設定 or コストの少ない経路がある場合はアップデート
            var needsUpdate = (node.cost < 0) || (node.cost > cost);
            if (needsUpdate) {
                node.cost = cost;
                node.previousNode = processNode;
            }
        }
    }

    console.log('Has been done to search path.');
    console.log(nodes);

    var goalNode = nodes[5];
    console.log('Shoten cost is ' + goalNode.cost);

    console.log('Shoten path');

    console.log('=====================');
    var path = 'Goal -> ';
    var currentNode = goalNode;
    while(true) {
        var nextNode = currentNode.previousNode;
        if (!nextNode) {
            path += ' Start';
            break;
        }
        path += nextNode.id + ' -> ';
        currentNode = nextNode;
    }

    console.log(path);
    console.log('=====================');
}

// Start this program.
main();