プログラミングとイラストレーション » ダイクストラ法による最短コスト探索2|HTML5
プログラミングとイラストレーション > HTML5 > ダイクストラ法による最短コスト探索2|HTML5

ダイクストラ法による最短コスト探索2|HTML5

ダイクストラ法による最短コスト探索

前回と同じような、ダイクストラ法による最短コスト(ルート)の探索を導き出すアルゴリズムを再び、JavaScriptでコーディングしました。

ここでは、n2というノードが出発点、n24というノードが終着点となっています。両者とも自由に他のノードに置き換えることができます。エッジのコストはすべて1にしています。コードを実行すると、上記の図のような経路が導き出されます。

ダイクストラ法による最短コスト探索2(HTML5, JavaScript) : デモ

ダイクストラ法による最短コスト探索2(HTML5, JavaScript) : ZIPファイル(45kb)

1.HTML

<!DOCTYPE html>
<html>
<head>
    <meta charset="utf-8">
    <meta http-equiv="X-UA-Compatible" content="IE=edge">
    <meta name="viewport" content="width=device-width, initial-scale=1, minimum-scale=1, maximum-scale=1, user-scalable=no">
    <title>ダイクストラ法 最短コスト(ルート)探索</title>
    <script>
        // ダイクストラ法 最短ルート探索
        var nodes = [];
        var nodeDone = null;
 
        function CreateNode(node){
            this.node = node;
            this.cost = -1;
            this.done = false;
            this.previousNode = null;
            this.nextNode = null;
            this.edgesTo = [];
            this.edgesCost = [];
        }
 
        // ノードを作る
        var node1 = new CreateNode(1);
        var node2 = new CreateNode(2);
        var node3 = new CreateNode(3);
        var node4 = new CreateNode(4);
        var node5 = new CreateNode(5);
        var node6 = new CreateNode(6);
        var node7 = new CreateNode(7);
        var node8 = new CreateNode(8);
        var node9 = new CreateNode(9);
        var node10 = new CreateNode(10);
        var node11 = new CreateNode(11);
        var node12 = new CreateNode(12);
        var node13 = new CreateNode(13);
        var node14 = new CreateNode(14);
        var node15 = new CreateNode(15);
        var node16 = new CreateNode(16);
        var node17 = new CreateNode(17);
        var node18 = new CreateNode(18);
        var node19 = new CreateNode(19);
        var node20 = new CreateNode(20);
        var node21 = new CreateNode(21);
        var node22 = new CreateNode(22);
        var node23 = new CreateNode(23);
        var node24 = new CreateNode(24);
        var node25 = new CreateNode(25);
 
 
        // 各ノードから連結する他のノードとそのコストを設定する
        node1.edgesTo.push(node2,node6,node7);
        node1.edgesCost.push(1,1,1);
        nodes.push(node1);
 
        node2.edgesTo.push(node1,node3,node6,node7,node8);
        node2.edgesCost.push(1,1,1,1,1);
        nodes.push(node2);
 
        node3.edgesTo.push(node2,node4,node7,node8,node9);
        node3.edgesCost.push(1,1,1,1,1);
        nodes.push(node3);
 
        node4.edgesTo.push(node3,node5,node8,node9,node10);
        node4.edgesCost.push(1,1,1,1,1);
        nodes.push(node4);
 
        node5.edgesTo.push(node4,node9,node10);
        node5.edgesCost.push(1,1,1);
        nodes.push(node5);
 
        node6.edgesTo.push(node1,node2,node7,node11,node12);
        node6.edgesCost.push(1,1,1,1,1);
        nodes.push(node6);
 
        node7.edgesTo.push(node1,node3,node6,node8,node11,node12,node13);
        node7.edgesCost.push(1,1,1,1,1,1,1);
        nodes.push(node7);
 
        node8.edgesTo.push(node2,node3,node4,node7,node9,node12,node13,node14);
        node8.edgesCost.push(1,1,1,1,1,1,1,1,1);
        nodes.push(node8);
 
        node9.edgesTo.push(node3,node4,node5,node8,node10,node13,node14,node15);
        node9.edgesCost.push(1,1,1,1,1,1,1,1);
        nodes.push(node9);
 
        node10.edgesTo.push(node4,node5,node9,node15);
        node10.edgesCost.push(1,1,1,1);
        nodes.push(node10);
 
        node11.edgesTo.push(node6,node7,node12,node16,node17);
        node11.edgesCost.push(1,1,1,1,1);
        nodes.push(node11);
 
        node12.edgesTo.push(node6,node7,node8,node11,node13,node16,node17,node18);
        node12.edgesCost.push(1,1,1,1,1,1,1,1);
        nodes.push(node12);
 
        node13.edgesTo.push(node7,node8,node9,node12,node14,node17,node18,node19);
        node13.edgesCost.push(1,1,1,1,1,1,1,1);
        nodes.push(node13);
 
        node14.edgesTo.push(node8,node9,node10,node13,node15,node18,node19,node20);
        node14.edgesCost.push(1,1,1,1,1,1,1,1);
        nodes.push(node14);
 
        node15.edgesTo.push(node9,node10,node14,node19,node20);
        node15.edgesCost.push(1,1,1,1,1);
        nodes.push(node15);
 
        node16.edgesTo.push(node11,node12,node17,node21,node22);
        node16.edgesCost.push(1,1,1,1,1);
        nodes.push(node16);
 
        node17.edgesTo.push(node11,node12,node13,node16,node18,node21,node22,node23);
        node17.edgesCost.push(1,1,1,1,1,1,1,1);
        nodes.push(node17);
 
        node18.edgesTo.push(node12,node13,node14,node17,node19,node22,node23,node24);
        node18.edgesCost.push(1,1,1,1,1,1,1,1);
        nodes.push(node18);
 
        node19.edgesTo.push(node13,node14,node15,node18,node20,node23,node24,node25);
        node19.edgesCost.push(1,1,1,1,1,1,1,1);
        nodes.push(node19);
 
        node20.edgesTo.push(node14,node15,node19,node24,node25);
        node20.edgesCost.push(1,1,1,1,1);
        nodes.push(node20);
 
        node21.edgesTo.push(node16,node17,node22);
        node21.edgesCost.push(1,1,1);
        nodes.push(node21);
 
        node22.edgesTo.push(node16,node17,node18,node21,node23);
        node22.edgesCost.push(1,1,1,1,1);
        nodes.push(node22);
 
        node23.edgesTo.push(node17,node18,node19,node22,node24);
        node23.edgesCost.push(1,1,1,1,1);
        nodes.push(node23);
 
        node24.edgesTo.push(node18,node19,node20,node23,node25);
        node24.edgesCost.push(1,1,1,1,1);
        nodes.push(node24);
 
        node25.edgesTo.push(node19,node20,node24);
        node25.edgesCost.push(1,1,1);
        nodes.push(node25);
 
        var startNode = nodes[1]; // スタートノードの設定
        startNode.cost = 0; // スタートノードのコストに0を設定
        startNode.done = true; // スタートノードを訪問済みにする
 
        var goalNode = nodes[23]; // ゴールノードを設定
        var prevNode = null;
        var min = 0;
        var min2 = 0;
 
 
 
        // 最短ルートを探索
        function setSearchRoute(){
            min = 9999;
            for(var i=0; i<nodes.length; i++){
                // ノードが訪問済みの場合に実行
                if(nodes[i].done===true){       
                    for(var j=0; j<nodes[i].edgesTo.length; j++){
                        // 接続したノードが未訪問の場合に実行
                        if(nodes[i].edgesTo[j].done===false){
                            // 接続したノードまでの最短コストを計算
 
                            if(min>nodes[i].cost+nodes[i].edgesCost[j]){
                                // 接続したノードのコスト
                                min = nodes[i].cost+nodes[i].edgesCost[j];
                                //min = score+nodes[i].edgesCost[j];
                                // 最短コストの始点のノード
                                prevNode = nodes[i];
                                // 最短コストの最終のノード
                                nodes[i].nextNode = nodes[i].edgesTo[j].node;
                                // 最短コストで決まった接続ノード
                                nodeDone = nodes[i].edgesTo[j];
                            }
                        }
                    }
                }
            }
        }
        var count = 0;
        while(goalNode.done==false){
            count++;
            setSearchRoute();
            // 最短に接続したノードを訪問済みにする
            nodeDone.done = true;
            // 最短に接続したノードのコストに最短コストを設定
            nodeDone.cost = min;
            // 最短コストの始点のノードを接続したノードに設定
            nodeDone.previousNode = prevNode;
        }
        console.log("count",count); 
 
        var path = '最短経路: Start ';
        var currentNode = goalNode;
        var route = [];
        while(currentNode.previousNode) {
            var nextNode = currentNode.previousNode;
            currentNode = nextNode;
            route.unshift(nextNode.node);
        }
 
        for(var i=0; i<route.length; i++){
            path += route[i] + ' -> ';
        }
        path += 'Goal(' + goalNode.node + ')';
 
        console.log('最短コスト: ' + goalNode.cost);
        console.log(path);
 
        window.onload = function() {
            var element = document.getElementById("result");
            element.innerHTML = "最短コスト: " +  goalNode.cost + "<br />" + path + "<br />探索回数: " + count;
        }
    </script>
</head>
<body>
    <img style="width:500px;" src="dijkstra2.png" alt="ダイクストラ法">
    <p id="result"></p>
</body>
</html>

コメントを残す

メールアドレスが公開されることはありません。 * が付いている欄は必須項目です

コメントフィード

トラックバック URL : http://www.htmlcode.jp/%e3%83%80%e3%82%a4%e3%82%af%e3%82%b9%e3%83%88%e3%83%a9%e6%b3%95%e3%81%ab%e3%82%88%e3%82%8b%e6%9c%80%e7%9f%ad%e3%82%b3%e3%82%b9%e3%83%88%e6%8e%a2%e7%b4%a2%ef%bc%92%ef%bd%9chtml5/trackback/