다익스트라 알고리즘(Dijkstra's Algorithm)

✅ 다익스트라 알고리즘(Dijkstra's Algorithm)이란?

그래프 내의 한 출발점에서 모든 다른 노드까지의 최단 경로를 찾는 데 사용되는 알고리즘으로 가중치가 있는 그래프에서 각 노드 사이의 최단 경로를 찾을 때 효과적으로 사용된다.

 

사용 사례

도로 네트워크 경로 탐색: 다익스트라 알고리즘은 GPS 시스템과 네비게이션 앱에서 사용된다. 운전자가 출발지와 목적지를 입력하면, 다익스트라 알고리즘을 활용하여 최단 경로와 예상 도착 시간을 계산하고 제공한다.

 

인터넷 라우팅: 다익스트라 알고리즘은 데이터 패킷을 최적 경로로 전달하는 라우팅 프로토콜에서 사용된다. 네트워크 노드 간의 연결을 나타내는 그래프에서 최단 경로를 계산하여 데이터의 효율적인 전달을 도와준다.

 

공항 및 항구 관리: 항공국 및 항구 관리자들은 비행기나 선박의 이동 경로를 최적화하기 위해 다익스트라 알고리즘을 사용한다. 이를 통해 운송 수단의 스케줄링 및 자원 할당을 효율적으로 관리할 수 있다.

 

소셜 네트워크 분석: 소셜 네트워크에서 다익스트라 알고리즘은 친구 추천 및 정보 전파 분석에 사용된다. 어떤 사람과 다른 사람 사이의 최단 경로를 찾아 친구 추천 알고리즘을 개선하거나 정보 전파의 효과를 연구할 수 있다.

 

그래프의 두 지점 사이의 최단 거리를 찾기 전에 먼저 해야할 일은 vertex 사이에 값을 부여해서 그 경로의 가중치를 알 수 있게 해야한다.

 

가중치 그래프 예시

class WeightedGraph {
    constructor() {
        this.adjacencyList = {};
    }
    addVertex(vertex) {
        if(!this.adjacencyList[vertex]) this.adjacencyList[vertex] = []
    }
    addEdge(vertex1, vertex2, weight) {
        this.adjacencyList[vertex1].push({node:vertex2, weight})
        this.adjacencyList[vertex2].push({node:vertex1, weight})
        
    }
}

위는 그래프에 가중치를 추가하여 가중치 그래프를 구현한 간단한 예이다. 우선순위 큐 구현 예시를 살펴보자. 결코 좋은 코드는 아니며 아주 기본적인 예시다.

class PriorityQueue{
    constructor() {
        this.values = [];
    }
    enqueue(val, priority) {
        this.values.push({val,priority});
        this.sort()
    }
    dequeue() {
        return this.values.shift()
    }
    sort() {
        this.values.sort((a,b) => a.priority - b.priority)
    }
}

다익스트라 알고리즘 의사코드

• 시작 vertex와 끝 vertex를 받는 함수를 선언한다.
• 객체를 생성하고(distances라고 부르는) 모든 vertex를 key로 하여 infinity 값으로 초기화 하며, 시작 vertex의 값은 0으로 설정한다.
• 모든 값들을 distances 객체에서 설정을 한 뒤에, 새로운 우선순위 큐를 만들고 빈 상태로 설정해 준다. 거기에 infinity인 vertex를 큐에 추가하고, 시작 vertex의 경우는 시작점이기 때문에 0으로 설정하여 큐에 추가한다.
• previous 객체를 추가하고 해당 객체에 인접 리스트의 모든 vertex의 key를 설정하고 각 프로퍼티의 값들은 null로 설정한다.
• 큐에 대기열이 있는 한 loop를 한다.
  • 우선순위 큐로부터 vertex를 dequeue한다.
  • 만약 vertex가 끝 vertex와 같다면 끝난다!
  • 그렇지 않으면 해당 정점의 인접 목록에 있는 각 값을 순환한다.
    • 시작 vertex와 vertex 사이의 거리를 계산한다.
    • 만약 거리가 최근에 저장된 거리보다 작다면
      • 더 작은 거리 값으로 distances 객체를 업데이트한다.
      • 해당 vertex를 포함하도록 previous 객체를 업데이트 한다.
      • 시작 노드로부터의 전체 거리로 정점을 enqueue한다.

구현

Dijkstra(start, finish){
    const nodes = new PriorityQueue();
    const distances = {};
    const previous = {};
    let path = [] //to return at end
    let smallest;
    
    // 초기값 설정
    // distances: 출발점 0, 나머지 Infinity
    // nodes(우선순위 큐): vertex와 가중치가 0 [{vla: vertex, priority: 0}...]
    // previous: {vertex: null,...}
    for(let vertex in this.adjacencyList){
        if(vertex === start){
            distances[vertex] = 0;
            nodes.enqueue(vertex, 0);
        } else {
            distances[vertex] = Infinity;
            nodes.enqueue(vertex, Infinity);
        }
        previous[vertex] = null;
    }
	// 방문해야할 노드가 있다면
    while(nodes.values.length){
        smallest = nodes.dequeue().val;
        if(smallest === finish){
                //WE ARE DONE
                //BUILD UP PATH TO RETURN AT END
            while(previous[smallest]){
                path.push(smallest);
                smallest = previous[smallest];
            }
            break;
        } 
        if(smallest || distances[smallest] !== Infinity){
            for(let neighbor in this.adjacencyList[smallest]){
                // 각 노드들의 인접 노드를 찾음.
                let nextNode = this.adjacencyList[smallest][neighbor];
                // 인접 노드들에 대한 새로운 거리를 계산함.
                let candidate = distances[smallest] + nextNode.weight;
                let nextNeighbor = nextNode.node;
                if(candidate < distances[nextNeighbor]){
                    distances[nextNeighbor] = candidate;
                    previous[nextNeighbor] = smallest;
                    nodes.enqueue(nextNeighbor, candidate);
                }
            }
        }
    }
    return path.concat(smallest).reverse();     
}

 

우선순위 큐 성능 향상

class Node {
    constructor(val, priority) {
        this.val = val;
        this.priority = priority;
    }
}

class PriorityQueue {
    constructor() {
        this.values = [];
    }

    enqueue(val, priority) {
        let newNode = new Node(val,priority);
        this.values.push(newNode)
        this.bubbleUp();
    }
    bubbleUp() {
        let idx = this.values.length - 1;
        const element = this.values[idx];
        while (idx > 0) {
            let parentIdx = Math.floor((idx - 1) / 2);
            let parent = this.values[parentIdx];
            if (element.priority >= parent.priority)
                break;
            this.values[parentIdx] = element;
            this.values[idx] = parent;
            idx = parentIdx;
        }
    }
    dequeue() {
        const min = this.values[0];
        const end = this.values.pop();
        if (this.values.length > 0) {
            this.values[0] = end;
            this.sinkDown();
        }
        return min;
    }

    sinkDown() {
        let idx = 0;
        const length = this.values.length;
        while (true) {
            const element = this.values[idx];
            const leftChildIdx = 2 * idx + 1;
            const rightChildIdx = 2 * idx + 2;
            let leftChild;
            let rightChild;
            let swap = null;

            if (leftChildIdx < length) {
                leftChild = this.values[leftChildIdx];
                if (leftChild.priority < element.priority) {
                    swap = leftChildIdx;
                }
            }

            if (rightChildIdx < length) {
                rightChild = this.values[rightChildIdx];
                if ((swap === null && rightChild.priority < element.priority) || (swap !== null && rightChild.priority < leftChild.priority)) {
                    swap = rightChildIdx;
                }
            }
            if (swap === null)
                break;

            [this.values[idx],this.values[swap]] = [this.values[swap], this.values[idx]];
            idx = swap;
        }
    }
}