ダイクストラ法による最短コスト(経路)探索|HTML5

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

ダイクストラ法による最短コスト、または最短ルートの探索を導き出すアルゴリズムをJavaScriptでコーディングしました。

ここでは、n1というノードが出発点、n8というノードが終着点となっています。両者とも自由に他のノードに置き換えることができます。ぜひ試してみてください。コードを実行すると、上記の図のような経路が導き出されます。

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

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

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);

		// 各ノードから連結する他のノードとそのコストを設定する
		node1.edgesTo.push(node2,node3,node4);
		node1.edgesCost.push(200,1000,550);
		nodes.push(node1);

		node2.edgesTo.push(node1,node5);
		node2.edgesCost.push(200,800);
		nodes.push(node2);

		node3.edgesTo.push(node1,node4,node6,node7);
		node3.edgesCost.push(1000,120,250,330);
		nodes.push(node3);

		node4.edgesTo.push(node1,node3,node5,node8);
		node4.edgesCost.push(550,120,300,880);
		nodes.push(node4);

		node5.edgesTo.push(node2,node4,node8);
		node5.edgesCost.push(800,300,450);
		nodes.push(node5);

		node6.edgesTo.push(node3,node6);
		node6.edgesCost.push(250,120);
		nodes.push(node6);

		node7.edgesTo.push(node3,node6,node8);
		node7.edgesCost.push(330,120,130);
		nodes.push(node7);

		node8.edgesTo.push(node4,node5,node7);
		node8.edgesCost.push(880,450,130);
		nodes.push(node8);

		var startNode = nodes[0]; // スタートノードの設定
		startNode.cost = 0; // スタートノードのコストに0を設定
		startNode.done = true; // スタートノードを訪問済みにする

		var goalNode = nodes[7]; // ゴールノードを設定
		var prevNode = null;
		var min = 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];
								// 最短コストの始点のノード
								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;
		}
	</script>
</head>
<body>
	<img style="width:500px; height: 500px;" src="dijkstra.png" alt="ダイクストラ法 ">
	<p id="result"></p>
</body>
</html>

コメントを残す

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