최단 경로 알고리즘(다익스트라, 플로이드-워셜)

최단 경로 알고리즘

가장 짧은 경로를 찾는 알고리즘

• 각 지점은 그래프에서 노드로 표현
• 지점 간 연결된 도로는 그래프에서 간선으로 표현

다양한 문제 상황

• 한 지점에서 다른 한 지점까지의 최단 경로 → BFS 이용
• 한 지점에서 다른 모든 지점까지의 최단 경로 → 다익스트라 알고리즘
• 모든 지점에서 다른 모든 지점까지의 최단 경로 → 플로이드 워셜 알고리즘

최단 경로 알고리즘 동작 과정

1. 최단 거리 테이블은 각 노드에 대한 현재까지의 최단 거리 정보를 가진다.
2. 처리 과정에서 더 짧은 경로를 찾으면 더 짧은 경로로 값을 갱신

 

다익스트라 알고리즘

• 특정한 노드에서 출발해서 다른 모든 노드로 가는 최단 경로 계산
• 다익스트라 알고리즘은 음의 간선이 없을 때 정상적으로 동작
  - 현실 세계의 간선은 음의 간선으로 표현X
  - 음의 간선이 포함될 때는 벨만 포드 알고리즘 사용
• 그리디 알고리즘으로 분류됨 → 매 상황에서 가장 비용이 적은 노드를 선택해 임의의 과정 반복
• 시간 복잡도: O(ElogV)
  - 노드 하나씩 꺼내 검사하는 반복문은 노드의 개수 V 이상의 횟수로 처리X
  - E개의 원소를 우선순위 큐에 넣었다가 모두 빼내는 연산과 매우 유사

동작 과정

1. 출발 노드 설정
2. 최단 거리 테이블 초기화
3. 방문하지 않은 노드 중에서 최단 거리가 가장 짧은 노드 선택
4. 해당 노드를 거쳐 다른 노드로 가는 비용 계산해서 최단 거리 테이블 갱신
   - 최단 거리 테이블을 직접 갱신하지 않고, 우선순위 큐에 삽입하는 방식 사용
5. 위 과정에서 3번과 4번 반복

우선순위 큐: 우선순위가 가장 높은 데이터를 가장 먼저 삭제하는 자료구조
- 힙 이용해서 구현
1) 최소 힙: 부모 노드는 항상 자식 노드보다 값이 작아야 함
2) 최대 힙: 부모 노드는 항상 자식 노드보다 크거나 같아야 함
- 시간 복잡도: O(logN)
- JS에서는 우선순위 큐 라이브러리 제공 X

특징

• 단계를 거치며 한 번 처리된 노드의 최단 거리는 고정되어 더 이상 바뀌지 않음
• 다익스트라 알고리즘 수행한 뒤에 테이블에 각 노드까지의 최단 거리 정보가 저장됨
• 단계마다 방문하지 않은 노드 중에서 최단 거리가 가장 짧은 노드 선택

소스 코드 예시

• 최소 힙 → 최댓값 구하기
• 최대 힙 → 최솟값 구하기

최소 힙 구현

• 부모 노드 인덱스 = (자식 노드 인덱스 - 1) / 2
• 왼쪽 자식 노드 인덱스 = (부모 노드 인덱스*2) + 1
• 오른쪽 자식 노드 인덱스 = (부모 노드 인덱스*2) + 2

 

 

 

 

class PriorityQueue {
    constructor() {
        this.heap = []; // 최소 힙
    }
    getParentIdx = (childIdx) => Math.floor((childIdx - 1) / 2);
    getLeftChildIdx = (parentIdx) => parentIdx * 2 + 1;
    getRightChildIdx = (parentIdx) => parentIdx * 2 + 2;
    getLength = () => this.heap.length;

    enqueue = (node, cost) => {
        this.heap.push({ node: node, cost: cost }); // 마지막에 새 원소 추가

        let currentIdx = this.heap.length - 1; // 새 원소 인덱스
        while (currentIdx > 0) {
            const parentIdx = this.getParentIdx(currentIdx);
            if (cost >= this.heap[parentIdx].cost) break; // 자식 노드가 더 큰 경우 패스

            // 자식 노드가 더 작은 경우 위치 swap
            [this.heap[parentIdx], this.heap[currentIdx]] = [this.heap[currentIdx], this.heap[parentIdx]];
            currentIdx = parentIdx;
        }
    };
    dequeue = () => {
        if (this.getLength() === 0) return undefined;
        else if (this.getLength() === 1) return this.heap.pop();
        else {
            const item = this.heap[0];
            this.heap[0] = this.heap.pop(); // 마지막 원소 루트로 이동

            let currentIdx = 0;
            while (currentIdx < this.getLength()) {
                const leftChildIdx = this.getLeftChildIdx(currentIdx);
                const rightChildIdx = this.getRightChildIdx(currentIdx);

                // 왼쪽 자식과 오른쪽 자식 중에 더 작은 원소랑 Swap
                let nextIdx = currentIdx;
                if (leftChildIdx < this.getLength() && this.heap[leftChildIdx].cost < this.heap[nextIdx].cost)
                    nextIdx = leftChildIdx;
                if (rightChildIdx < this.getLength() && this.heap[rightChildIdx].cost < this.heap[nextIdx].cost)
                    nextIdx = rightChildIdx;

                if (nextIdx === currentIdx) break; // 부모 원소가 더 작은 경우 중단

                [this.heap[nextIdx], this.heap[currentIdx]] = [this.heap[currentIdx], this.heap[nextIdx]];
                currentIdx = nextIdx;
            }
            return item;
        }
    };
}

const fs = require('fs');
const input = fs.readFileSync('/dev/stdin').toString().split('\n');

const [V, E] = input[0].split(' ').map(Number); // 정점: V, 간선: E
const K = +input[1]; // 시작 정점 번호
const graph = Array.from({ length: V + 1 }, () => []);
for (let i = 0; i < E; i++) {
    const [u, v, w] = input[i + 2].split(' ').map(Number);
    graph[u].push([v, w]);
}

const minCost = Array.from({ length: V + 1 }, () => Number.MAX_SAFE_INTEGER);
const pq = new PriorityQueue();
pq.enqueue(K, 0);
minCost[K] = 0; // 시작 노드는 0으로 설정

while (pq.getLength() > 0) {
    const { node, cost } = pq.dequeue();
    for (const [next, value] of graph[node]) {
        const newCost = cost + value;
        if (minCost[next] <= newCost) continue;
        pq.enqueue(next, newCost);
        minCost[next] = newCost;
    }
}

for (let c = 1; c <= V; c++) {
    console.log(minCost[c] === Number.MAX_SAFE_INTEGER ? 'INF' : minCost[c]);
}

 

 

플로이드-워셜 알고리즘

모든 노드에서 다른 모든 노드까지의 최단 경로 모두 계산

• 한 번 실행하여 모든 노드 간 최단 경로를 구할 수 있음. 또한, 음의 간선도 사용 가능
• 매 단계마다 방문하지 않은 노드 중에 최단 거리를 갖는 노드를 찾는 과정 필요 X
• 2차원 테이블에 최단 거리 정보 저장
• DP 유형에 속함

동작 과정

• 각 단계마다 특정한 노드 K를 거쳐 가는 경우 확인 → A에서 B로 가는 최단 거리보다 A에서 K를 거쳐 B로 가는 거리가 더 짧은지 검사
• D[A][B] = MIN(D[A][B], D[A][K]+D[K][B])

코드

const INF = Number.MAX_SAFE_INTEGER;
const N = 5; // 노드 개수

// graph[i][j]는 i에서 j로 가기 위한 초기 비용(간선 비용)
// 자기 자신으로 가는 비용은 0으로 초기화
const graph = [
    [INF, INF, INF, INF, INF, INF], // 인덱스 0은 사용하지 않음
    [INF, 0, 1, 5, INF, INF], // 1번 노드 간선들
    [INF, 7, 0, 2, 2, INF], // 2번 노드 간선들
    [INF, 2, INF, 0, INF, 6], // 3번 노드 간선들
    [INF, INF, 2, INF, 0, INF], // 4번 노드 간선들
    [INF, INF, INF, 1, INF, 0], // 5번 노드 간선들
];

// 점화식에 따라 플로이드 워셜 알고리즘 수행
for (let k = 1; k <= N; k++) {
    for (let a = 1; a <= N; a++) {
        for (let b = 1; b <= N; b++) {
            const cost = graph[a][k] + graph[k][b];
            graph[a][b] = Math.min(graph[a][b], cost);
        }
    }
}