ダイクストラアルゴリズム
この記事では、ダイクストラアルゴリズムの概念と動作方式、そしてProgrammersの[迷路脱出]問題について説明します。
ダイクストラアルゴリズムは、グラフのある頂点から他のすべての頂点までの最短経路を求めるアルゴリズムです。
コンピューターネットワークやナビゲーションなど、経路探索が必要なさまざまな分野で使えます。
1. 基本概念
ダイクストラアルゴリズムは、次のような核となる概念に基づいています。
重み付きグラフ : 辺ごとに負でない重みが存在するグラフ
出発点 : 最短経路を開始するノード
距離配列 : 各ノード間の最短距離
優先度付きキュー : 訪問するノードを、累積コストが小さい順に並べるキュー
頂点の数をV、辺の数をEとすると、ダイクストラアルゴリズムの時間計算量は次のように計算します。
優先度付きキューを使う場合、時間計算量はO(VlogV + ElogV)です。
各ループごとに、未訪問ノードのうち出発点から現在までの累積最短距離を優先度付きキューで更新するのに、O(VlogV)の時間がかかります。
各ノードごとに、隣接ノードの最短距離を更新するのに、O(ElogV)の時間がかかります。
もし負の重みが存在する場合は、ベルマン-フォードアルゴリズムを使う必要があります。
2. 動作方式
ダイクストラアルゴリズムは、通常次の手順に従います。
距離配列の初期化
出発ノードの距離は0、残りのノードは無限大に設定します。

最も近いノードの選択
キューの出発点と隣接するノードを選んで、キューに追加します。

距離の更新
選択したノードの隣接ノードを確認しながら、出発点から未訪問の経路が見つかれば、距離配列を更新し続けます。





すべてのノードを訪問するか、それ以上更新する経路がなくなったら、アルゴリズムを終了します。

この過程で、より短い累積距離を持つ経路から先に探索するために優先度付きキュー(Priority Queue)を使うので、先に訪問したノードの累積距離の値が最短距離の値になります。
3. 優先度付きキュー
ダイクストラアルゴリズムは、優先度付きキューでなくても、sort関数を毎回実行して実装することができます。しかし、時間計算量がよくないため、優先度付きキューを活用すべきです。そのため、JavaScriptで効率的な優先度付きキューを実装できる必要があります。優先度付きキューのサンプルコードをお見せします。
class PriorityQueue { constructor(comparator = (a, b) => a > b) { this.heap = []; this.comparator = comparator; // boolean comparator } size() { return this.heap.length; } isEmpty() { return this.size() === 0; } peek() { return this.heap[0]; } push(value) { this.heap.push(value); this._heapifyUp(); } pop() { if (this.isEmpty()) return null; const top = this.peek(); const last = this.heap.pop(); if (!this.isEmpty()) { this.heap[0] = last; this._heapifyDown(); } return top; } _heapifyUp() { let index = this.size() - 1; const element = this.heap[index]; while (index > 0) { const parentIndex = Math.floor((index - 1) / 2); const parent = this.heap[parentIndex]; if (!this.comparator(element, parent)) break; this.heap[index] = parent; index = parentIndex; } this.heap[index] = element; } _heapifyDown() { let index = 0; const length = this.size(); const element = this.heap[0]; while (true) { const leftIndex = 2 * index + 1; const rightIndex = 2 * index + 2; let swapIndex = null; if (leftIndex < length && this.comparator(this.heap[leftIndex], element)) { swapIndex = leftIndex; } if ( rightIndex < length && ((swapIndex === null && this.comparator(this.heap[rightIndex], element)) || (swapIndex !== null && this.comparator(this.heap[rightIndex], this.heap[leftIndex]))) ) { swapIndex = rightIndex; } if (swapIndex === null) break; this.heap[index] = this.heap[swapIndex]; index = swapIndex; } this.heap[index] = element; }}4. 実践例題 - [Programmers]迷路脱出

迷路脱出問題で、ダイクストラアルゴリズムを使ってどのように問題を解いたのか、コードをお見せします。問題の説明は長いので、別途リンクを添付します。
問題の説明 : 出発地から目的地まで行ける最短距離の値を求める必要があります。ノードには通常ノードと罠ノードがあります。
問題のポイント :
ダイクストラアルゴリズムで、出発地Xから目的地Yまでの距離を求める必要があります。
辺には方向があります。
AノードとBノードの間には、複数の辺が存在することがあります。
ノードには罠のノードが存在し、罠のノードに到着すると、罠ノードにつながっているすべての辺の向きが逆になります。
出発地と到着地は罠ノードではありません。
常に出発地から到着地まで到達可能です。
解法のポイント:
出発地Xから全ノードの距離を求めるのではなく、特定のXノードとの距離だけを求めたら終了する必要があります。
AノードとBノードの間の辺は、方向ごとに最小値の辺だけを残す必要があります。
到着地がない場合は考えなくて大丈夫です。(見つからない場合の例外処理は不要です。)
罠があるため、同じノードを2回踏むケースが生じます。
辺が切り替わるノードを知るために、ノードと辺の情報に加えて、追加の状態値を保存する必要がありそうです。
以下は、私が最初に正解として提出したコードです。急いで解いたので、変数名からしてすべてめちゃくちゃですね。上の[3. 優先度付きキュー]と下のコードの優先度付きキューの違いは、literal objectで実装した点です。速度はどちらの方法も同じくらいでしたが、V8エンジンの最適化ではliteral objectのほうが不利になることがあるそうです。(おそらくV8エンジンの最適化方式上、同じ型の繰り返しではないため、型テンプレートのキャッシングが起きないのだろうと個人的に推測しています。間違っているかもしれないので、ご自身で学習してみてください。)
class PriorityQueue { constructor(oper) { this.items = {}; this.tail = 0; this.oper = oper; } push(item) { const pushIndex = this.tail++; this.items[pushIndex] = item; this.heapUp(pushIndex); } pop() { if (this.isEmpty()) return undefined; const item = this.items[0]; const lastIndex = --this.tail; [this.items[0], this.items[lastIndex]] = [this.items[lastIndex], this.items[0]]; delete this.items[lastIndex]; if (!this.isEmpty()) this.heapDown(0); return item; } isEmpty() { return 0 === this.tail; } size() { return this.tail; } getParentIndex(index) { const parentIndex = Math.floor((index-1)/2); if(parentIndex < 0) return null; return parentIndex; } swapParent(index) { const parentIndex = Math.floor((index-1)/2); if(parentIndex < 0) return null; [this.items[index], this.items[parentIndex]] = [this.items[parentIndex],this.items[index]] } heapUp(index) { const item = this.items[index]; const parentIndex = this.getParentIndex(index) if(parentIndex === null) return; const parent = this.items[parentIndex]; if(this.oper(item, parent)){ this.swapParent(index); this.heapUp(parentIndex); } } heapDown(index) { const item = this.items[index]; const lIndex = index*2+1; const rIndex = index*2+2; if(this.tail <= lIndex) return; if(this.tail <= rIndex) { if(this.oper(this.items[lIndex],item)) [this.items[lIndex], this.items[index]] = [this.items[index], this.items[lIndex]] return this.heapDown(lIndex); } if(this.oper(this.items[lIndex],this.items[rIndex])) { if(this.oper(this.items[lIndex],item)) { [this.items[lIndex], this.items[index]] = [this.items[index], this.items[lIndex]] return this.heapDown(lIndex); } } else { if(this.oper(this.items[rIndex],item)) { [this.items[rIndex], this.items[index]] = [this.items[index], this.items[rIndex]] return this.heapDown(rIndex); } } }}// [現在位置, 移動距離]function solution(n, start, end, roads, traps) { const MAP = Array.from(Array(n+1),()=>Array(n+1).fill(0)) const visited = Array.from(Array(n+1),()=>[Math.infinite, Math.infinite]) roads.forEach((road)=>{ if(MAP[road[0]][road[1]] === 0) MAP[road[0]][road[1]]=road[2] else if(MAP[road[0]][road[1]] > road[2]) MAP[road[0]][road[1]] = road[2]; }) const queue = new PriorityQueue((item1,item2) => (item1[1] < item2[1])); queue.push([start,0,0,{},{}]) const trapsDict = traps.reduce((prev, trap)=>({...prev,[trap]:true}), {}) const answer = dik(queue, start, end, MAP, visited, trapsDict); return answer;}function dik(queue, start, end, Map, visited,traps) { const current = queue.pop(); // [位置, 移動距離, 回数, trapped] const [pos,dis,count,trapped,visited2] = current; const isTrap = traps[pos]; if(pos === end) return dis; if(count >= 2) return dik(queue, start, end, Map, visited, traps); if(dis > visited[pos][count]) return dik(queue, start, end, Map, visited, traps); visited[pos][count] = dis; const visitedCopy = {...visited2} if(visitedCopy[pos]) { visitedCopy[pos] += 1; } else { visitedCopy[pos] = 1; } const newTrapped = {...trapped}; if(isTrap){ newTrapped[pos] = newTrapped[pos]? 2: 1 } const newMap2 = [...Map[pos]]; if(isTrap && newTrapped[pos]!==2) { for(let i=1; i<newMap2.length; i++) { newMap2[i] = Map[i][pos]; } } Object.keys(trapped).forEach((trap)=> { if(newMap2[trap] === Map[trap][pos]) newMap2[trap] = Map[pos][trap]; else newMap2[trap] = Map[trap][pos]; }) newMap2.forEach((to,index)=> { if(to) { const visitTrapCount = newTrapped[index] ?? 0; const visitCount = visitedCopy[index] ?? 0; if(visitTrapCount>1) return; if(visitCount >1) return; queue.push([index,to+dis,visitCount,newTrapped,visitedCopy]) } }) return dik(queue, start, end, Map, visited, traps);}上のコードを、変数名も含めてもっとすっきり書き直してみます。
class PriorityQueue { constructor(comparator = (a, b) => a > b) { this.heap = []; this.comparator = comparator; } size() { return this.heap.length; } isEmpty() { return this.size() === 0; } peek() { return this.heap[0]; } push(value) { this.heap.push(value); this._heapifyUp(); } pop() { if (this.isEmpty()) return null; const top = this.peek(); const last = this.heap.pop(); if (!this.isEmpty()) { this.heap[0] = last; this._heapifyDown(); } return top; } _heapifyUp() { let index = this.size() - 1; const element = this.heap[index]; while (index > 0) { const parentIndex = Math.floor((index - 1) / 2); const parent = this.heap[parentIndex]; if (!this.comparator(element, parent)) break; this.heap[index] = parent; index = parentIndex; } this.heap[index] = element; } _heapifyDown() { let index = 0; const length = this.size(); const element = this.heap[0]; while (true) { const leftIndex = 2 * index + 1; const rightIndex = 2 * index + 2; let swapIndex = null; if (leftIndex < length && this.comparator(this.heap[leftIndex], element)) { swapIndex = leftIndex; } if ( rightIndex < length && ((swapIndex === null && this.comparator(this.heap[rightIndex], element)) || (swapIndex !== null && this.comparator(this.heap[rightIndex], this.heap[leftIndex]))) ) { swapIndex = rightIndex; } if (swapIndex === null) break; this.heap[index] = this.heap[swapIndex]; index = swapIndex; } this.heap[index] = element; }}// [現在位置, 累積距離, 訪問回数, 有効化されたトラップの状態, 訪問履歴]function solution(n, start, end, roads, traps) { const graph = Array.from({ length: n + 1 }, () => Array(n + 1).fill(0)); // [ノードを最初に踏んだときの最短距離, ノードを2回目に踏んだときの最短距離] const distanceRecord = Array.from({ length: n + 1 }, () => [Infinity, Infinity]); // グラフの初期化 roads.forEach(([from, to, cost]) => { if (graph[from][to] === 0 || graph[from][to] > cost) { graph[from][to] = cost; } }); const pq = new PriorityQueue((a, b) => a[1] < b[1]); pq.push([start, 0, 0, {}, {}]); const trapSet = traps.reduce((acc, trap) => ({ ...acc, [trap]: true }), {}); return dijkstra(pq, end, graph, distanceRecord, trapSet);}function dijkstra(pq, end, graph, distanceRecord, trapSet) { while (!pq.isEmpty()) { const current = pq.pop(); const [pos, totalDist, visitCount, activeTraps, visitHistory] = current; const isTrap = trapSet[pos]; if (pos === end) return totalDist; if (visitCount >= 2) continue; if (totalDist > distanceRecord[pos][visitCount]) continue; distanceRecord[pos][visitCount] = totalDist; // 訪問履歴の更新 const newVisitHistory = { ...visitHistory }; newVisitHistory[pos] = (newVisitHistory[pos] ?? 0) + 1; // トラップの有効化状態を更新 const newActiveTraps = { ...activeTraps }; if (isTrap) { newActiveTraps[pos] = newActiveTraps[pos] ? 2 : 1; } // 現在位置を基準に移動可能な辺 const nextEdges = [...graph[pos]]; if (isTrap && newActiveTraps[pos] !== 2) { for (let i = 1; i < nextEdges.length; i++) { nextEdges[i] = graph[i][pos]; } } // 他のトラップの影響を反映 Object.keys(activeTraps).forEach((trap) => { if (nextEdges[trap] === graph[trap][pos]) { nextEdges[trap] = graph[pos][trap]; } else { nextEdges[trap] = graph[trap][pos]; } }); // 移動 nextEdges.forEach((cost, nextPos) => { if (cost) { const trapVisitCount = newActiveTraps[nextPos] ?? 0; const nodeVisitCount = newVisitHistory[nextPos] ?? 0; if (trapVisitCount > 1) return; if (nodeVisitCount > 1) return; pq.push([nextPos, totalDist + cost, nodeVisitCount, newActiveTraps, newVisitHistory]); } }); } return -1; // 到達不可能}上のコードで、なぜこう変えたのか、なぜ変えなかったのか、解説を加えてみます。
上のコードで、ダイクストラアルゴリズムの説明と違う実装をした部分はあるでしょうか??
はい、そもそもすでに訪問したノードなら、本来は優先度付きキューにそのノードを入れないほうが速いと思います。しかし私は、罠のせいで2回訪問するケースまで考えているうちに、そこまで考えが及ばなかったようです。皆さんは、distanceRecord[nodeVisitCount][nextPos]がすでに訪問済みなら、最初からqueueに入れないように実装してください!!そのほうが速いと思います。
activeTrapsをなぜ別途一緒に渡すのですか?
newVisitHistoryとtrapsの情報だけでも発動した罠はわかりますが、発動した罠を探すのに時間がかかる可能性があると考えたので、別途Mapデータ型でactiveTrapsを持たせるようにしました。
グラフの辺の情報をN X M配列で持つと、メモリを使いすぎませんか?
はい、ノードの数が増えるとメモリを多く使います。そこで、Mapデータ型でノードごとに持つ辺を管理するようにすれば、メモリをかなり節約できます。しかし、そうするとノード間の辺の有無を確認しなければならないため、配列のindexでアクセスするよりは遅くなるでしょう。trade offの関係の中で、速度をより重視しました。
ダイクストラアルゴリズムの処理を、heapが空になるまで実行するwhile文に変えましたが、なぜ変えたのですか?
function再帰関数は、関数が呼び出されるたびにStack領域に関数が積み重なります。つまり、while文はScopeが新しくできるだけで済みますが、再帰関数で処理すると、関数が実行されるたびに実行コンテキストが作られる必要があり、その分コストが多くかかります。
もっと速く処理することはできないでしょうか?
どうでしょう??うーん、今のところ思いつくものはないですね。ビット演算をするにはarrayが長すぎるものばかりのようですし…ArrayBufferを使うにも、サイズが可変なデータ型を使っているので無理そうです。あえて探すなら、Workerを使えばいけるでしょうか..? よくわかりません。

