前回の記事では、生成するグラフが疎であったので連結リストを使用した。密グラフ向けに行列でも実装した。
■実装
// Graph //(密ではないが)前回のグラフと同じグラフを使用 var Vertexes = [ [0, 1, 3, 0, 0, 0],// s [0, 0, 1, 4, 0, 0],// 1 [0, 0, 0, 1, 0, 0],// 2 [0, 0, 0, 0, 1,10],// 3 [0, 0, 0, 0, 0, 1],// 4 [0, 0, 0, 0, 0, 0] // g ]; // initialize var dist = []; var pred = []; var visited = []; for(var i = 0; i < Vertexes.length; i++){ dist[i] = Number.POSITIVE_INFINITY; pred[i] = -1; visited[i] = false;// 訪問を記録する } dist[0] = 0;// start // search var dijkstraMX = function(){ var getMin = function(){ var tmp = Number.POSITIVE_INFINITY; for(var i = 0; i < Vertexes.length; i++){ if(visited[i] === false && dist[i] < tmp){ tmp = i; } } if(tmp === Number.POSITIVE_INFINITY){ tmp = null; } return tmp; } while(true){ var u = getMin();// 未訪問の中でスタートから最小の距離の頂点 // 「sから辿れない頂点しか残っていない場合」「未訪問が無い場合」はループ終了 if(dist[u] === Number.POSITIVE_INFINITY || u === null){break;} visited[u] = true; for(var i = 0; i < Vertexes[u].length; i++){ if(Vertexes[u][i] > 0){// 辺が存在している var neighbor = i;//隣接点(a) var weight = Vertexes[u][i];// (a)との辺の重み var newLength = dist[u] + weight;// (b) // 現在セットされている、スタート地点から隣接点までの距離が // 新しい経路での値より大きい時 if(newLength < dist[neighbor]){ dist[neighbor] = newLength; pred[neighbor] = u; } } } } } dijkstraMX(); // 最短経路 console.log(pred);// [-1, 0, 1, 2, 3, 4] // 最短距離 console.log(dist);// [0, 1, 2, 3, 4, 5]
グラフが疎である場合、行列を使用すると殆どの空間が0で埋められるので勿体無いね。
ピンバック: Tweets that mention JavaScriptでダイクストラ法(行列) - @blog.justoneplanet.info -- Topsy.com