JavaScriptでダイクストラ法
優先度つきキューを使用したダイクストラ法を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; }
TrackBack URL :
Comments (1)
[…] 事後に追加で15分位ググったら、ダイクストラ法のみならず JavaScriptでダイクストラ法 というベストマッチなエントリまで発見してしまい・・・ […]