최단 경로 문제

최단 경로 알고리즘 : 가장 짦은 경로를 찾는 알고리즘

 

다양한 문제 상황

 - 한 지점에서 다른 한 지점까지의 최단 경로

 - 한 지점에서 다른 모든 지점까지의 최단 경로

 - 모든 지점에서 다른 모든 지점까지의 최단 경로

 

각 지점은 그래프에서 노드로 표현

 

지점 간 연결된 도로는 그래프에서 간선으로 표현

 

최단 경로 알고리즘의 종류

 

다익스트라 최단 경로 알고리즘

플로이드 워셜,

벨만 포드 알고리즘

 

이 중 빨간색이 코딩 테스트에서 가장 많이 등장

 

다익스트라 최단 경로 알고리즘

 

특정한 노드에서 출발하여 다른 모든 노드로 가는 최단 경로를 계산

 

다익스트라 최단 경로 알고리즘은 '음의 간선'이 없을 때 정상적으로 동작

 - 현실 세계의 도로(간선)은 음의 간선으로 표현 X

 

다익스트라 최단 경로 알고리즘은 그리디 알고리즘으로 분류

 - 매 상황에서 가장 비용이 적은 노드를 선택해 임의의 과정을 반복

 

동작 과정

 

1. 출발 노드를 설정
2. 최단 거리 테이블을 초기화
3. 방문하지 않은 노드 중에서 최단 거리가 가장 짧은 노드를 선택
4. 해당 노드를 거쳐 다른 노드로 가는 비용을 계산하여 최단 거리 테이블을 갱신
5. 3번과 4번을 반복

※ 각 노드에 대한 현재까지의 최단 거리 정보를 1차원 리스트에 저장하며 리스트를 계속 갱신한다.

 

알고리즘 동작 과정에서 최단 거리 테이블은 각 노드에 대한 현재까지의 최단 거리 정보를 가지고 있다.

 

처리 과정에서 더 짧은 경로를 찾으면 '최단 경로'를 갱신

 

다익스트라 알고리즘 구현 방법 2가지

 

• 방법 1. 구현하기 쉽지만 느리게 동작하는 코드
• 방법 2. 구현하기에 조금 더 까다롭지만 빠르게 동작하는 코드

 

과정

 

• 1에서 출발한다.
• 1번 노드에서 다른 모든 노드로의 최단 거리 계산
• 초기 상태에서는 다른 모든 노드로 가는 최단 거리를 '무한'으로 초기화 (999,999,999 or 1e9)

방문하지 않은 노드 중 최단 거리가 가장 짧은 노드를 선택

 

 

STEP 1

출발 노드에서 출발 노드의 거리는 0으로 본다.

 

STEP 2

 

1. 1번 노드를 거쳐 다른 노드로 가는 비용을 계산 (2번, 3번, 4번 연결)

   1) 2번 : 0 + 2 = 2

   2) 3번 : 0 + 5 = 5

   3) 4번 : 0 + 1 = 1

 

2. 기존 테이블의 2, 3, 4번의 경로는 무한이었는데 더 짧은 경로를 찾았기 때문에 새로운 값으로 갱신한다.

 

이미 처리된 노드와 간선을 표시한다.

 

STEP 3

 

이후 모든 단계에서도 방문하지 않은 노드 중에서 최단 거리가 가장 짧은 노드를 선택해야 한다.

 

1. 4번 선택

 

2. 4번 노드를 거쳐 다른 노드로 가는 비용을 계산 (3번, 5번 연결)

   1) 3번 : 1 + 3 = 4

   2) 5번 : 1 + 1 = 2

 

3. 위 두 값이 기존의 리스트에 담겨 있던 값보다 작으므로 다음처럼 리스트가 갱신

 

STEP 4

 

1. 2번 선택 -> 2번과 5번까지의 최단 거리가 2로 같은데 이럴 때 일반적으로 번호가 더 작은 노드 선택

 

2. 4번 노드를 거쳐 다른 노드로 가는 비용을 계산 (3번, 4번)

   1) 3번 : 2 + 3 = 5

   2) 4번 : 2 + 2 = 4

 

3. 2번에서 출발하여 3번과 4번까지의 거리는 기존 계산한 거리보다 더 길다.

   1) 3번까지의 최단 거리 : 기존 4 vs 신규 5

   2) 4번까지의 최단 거리 : 기존 1 vs 신규 4

 

4. 때문에 최단 거리 테이블을 갱신하지 않는다.

 

STEP 5

 

1. 5번 선택

 

2. 5번 노드를 거쳐 다른 노드로 가는 비용을 계산 (3번, 6번)

   1) 3번 : 2 + 1 = 3

   2) 6번 : 2 + 2 = 4

 

4. 위 두 값이 기존의 리스트에 담겨 있던 값보다 작으므로 다음처럼 리스트가 갱신.

 

STEP 6

 

1. 3번 선택

 

2. 3번 노드를 거쳐 다른 노드로 가는 비용을 계산 (2번, 6번)

   1) 2번 : 3 + 3 = 6

   2) 6번 : 3 + 5 = 8

 

3. 3번에서 출발하여 2번, 6번까지의 거리는 기존 계산한 거리보다 더 길다.

   1) 2번까지의 최단 거리 : 기존 2 vs 신규 6

   1) 6번까지의 최단 거리 : 기존 4 vs 신규 8

 

4. 때문에 최단 거리 테이블을 갱신하지 않는다.

STEP 7

 

1. 6번 선택

 

2. 연결된 곳이 없기 때문에 pass

 

최단 거리 테이블이 의미하는 바

 

1번 노드로부터 출발했을 때 2~6번 노드까지 가기 위한 최단 경로가 각각 2, 3, 1, 2, 4라는 의미

 

'방문하지 않은 노드 중에서 가장 최단 거리가 짧은 노드를 선택' 하는 과정

 

이렇게 선택된 노드는 '최단 거리'가 완전히 선택된 노드이므로, 더 이상 알고리즘을 반복해도 최단 거리가 줄어들지 않는다.

 

 

한 단계당 하나의 노드에 대한 최단 거리를 확실히 찾는 것으로 이해

 

 

#include <vector>
#include <queue>
#include <iostream>

#define INF 1e9 // 무한을 의미하는 값으로 10억을 설정

using namespace std;

// 노드의 개수(N), 간선의 개수(M), 시작 노드 번호(Start)
// 노드의 개수는 최대 100,000개라고 가정
int n, m, start;
// 각 노드에 연결되어 있는 노드에 대한 정보를 담는 배열
vector<pair<int, int> > graph[100001];
// 방문한 적이 있는지 체크하는 목적의 배열 만들기
bool visited[100001];
// 최단 거리 테이블 만들기
int d[100001];

// 방문하지 않은 노드 중에서, 가장 최단 거리가 짧은 노드의 번호를 반환
int getSmallestNode() {
    int min_value = INF;
    int index = 0; // 가장 최단 거리가 짧은 노드(인덱스)
    for (int i = 1; i <= n; i++) {
        if (d[i] < min_value && !visited[i]) {
            min_value = d[i];
            index = i;
        }
    }
    return index;
}

void dijkstra(int start) {
    // 시작 노드에 대해서 초기화
    d[start] = 0;
    visited[start] = true;
    for (int j = 0; j < graph[start].size(); j++) {
        d[graph[start][j].first] = graph[start][j].second;
    }
    // 시작 노드를 제외한 전체 n - 1개의 노드에 대해 반복
    for (int i = 0; i < n - 1; i++) {
        // 현재 최단 거리가 가장 짧은 노드를 꺼내서, 방문 처리
        int now = getSmallestNode();
        visited[now] = true;
        // 현재 노드와 연결된 다른 노드를 확인
        for (int j = 0; j < graph[now].size(); j++) {
            int cost = d[now] + graph[now][j].second;
            // 현재 노드를 거쳐서 다른 노드로 이동하는 거리가 더 짧은 경우
            if (cost < d[graph[now][j].first]) {
                d[graph[now][j].first] = cost;
            }
        }
    }
}

int main(void) {
    cin >> n >> m >> start;

    // 모든 간선 정보를 입력받기
    for (int i = 0; i < m; i++) {
        int a, b, c;
        cin >> a >> b >> c;
        // a번 노드에서 b번 노드로 가는 비용이 c라는 의미
        graph[a].push_back({ b, c }); // pair
    }

    // 최단 거리 테이블을 모두 무한으로 초기화
    fill_n(d, 100001, INF);

    // 다익스트라 알고리즘을 수행
    dijkstra(start);

    // 모든 노드로 가기 위한 최단 거리를 출력
    for (int i = 1; i <= n; i++) {
        // 도달할 수 없는 경우, 무한(INFINITY)이라고 출력
        if (d[i] == INF) {
            cout << "INFINITY" << '\n';
        }
        // 도달할 수 있는 경우 거리를 출력
        else {
            cout << d[i] << '\n';
        }
    }
}

 

총 O(V)번에 걸쳐서 최단 거리가 가장 짧은 노드를 매번 선형 탐색 필요

전체 시간 복잡도는  O(V^2)

그러나 노드의 개수가 많아지면 비효율성을 야기할 수 있다.

 

우선순위 큐

우선순위가 가장 높은 데이터를 가장 먼저 삭제하는 자료구조

여러 개의 물건 데이터를 자료구조에 넣었다가 가치가 높은 물건 데이터부터 꺼내서 확인해야 하는 경우에 우선순위 큐를 사용할 수 있다.

 

최소 힙(Min Heap)과 최대 힙(Max Heap)이 있다.

우선순위 큐 구현 방식	삽입 시간	삭제 시간
리스트	O(1)	O(logN)
힙(Heap)	O(logN)	O(logN)

 

단계마다 방문하지 않은 노드 중에서 최단 거리가 가장 짧은 노드를 선택하기 위해 힙(Heap) 자료구조를 이용한다.

 

#include <iostream>
#include <vector>
#include <queue>

#define INF 1e9 // 무한을 의미하는 값으로 10억을 설정

using namespace std;

// 노드의 개수(N), 간선의 개수(M), 시작 노드 번호(Start)
// 노드의 개수는 최대 100,000개라고 가정
int n, m, start;
// 각 노드에 연결되어 있는 노드에 대한 정보를 담는 배열
vector<pair<int, int> > graph[100001];
// 최단 거리 테이블 만들기
int d[100001];

void dijkstra(int start) {
    priority_queue<pair<int, int> > pq;
    // 시작 노드로 가기 위한 최단 경로는 0으로 설정하여, 큐에 삽입
    pq.push({ 0, start });
    d[start] = 0;
    while (!pq.empty()) { // 큐가 비어있지 않다면
        // 가장 최단 거리가 짧은 노드에 대한 정보 꺼내기
        int dist = -pq.top().first; // 현재 노드까지의 비용 
        int now = pq.top().second; // 현재 노드
        pq.pop();
        // 현재 노드가 이미 처리된 적이 있는 노드라면 무시
        if (d[now] < dist) continue;
        // 현재 노드와 연결된 다른 인접한 노드들을 확인
        for (int i = 0; i < graph[now].size(); i++) {
            int cost = dist + graph[now][i].second;
            // 현재 노드를 거쳐서, 다른 노드로 이동하는 거리가 더 짧은 경우
            if (cost < d[graph[now][i].first]) {
                d[graph[now][i].first] = cost;
                pq.push(make_pair(-cost, graph[now][i].first));
            }
        }
    }
}

int main(void) {
    cin >> n >> m >> start;

    // 모든 간선 정보를 입력받기
    for (int i = 0; i < m; i++) {
        int a, b, c;
        cin >> a >> b >> c;
        // a번 노드에서 b번 노드로 가는 비용이 c라는 의미
        graph[a].push_back({ b, c });
    }

    // 최단 거리 테이블을 모두 무한으로 초기화
    fill(d, d + 100001, INF);

    // 다익스트라 알고리즘을 수행
    dijkstra(start);

    // 모든 노드로 가기 위한 최단 거리를 출력
    for (int i = 1; i <= n; i++) {
        // 도달할 수 없는 경우, 무한(INFINITY)이라고 출력
        if (d[i] == INF) {
            cout << "INFINITY" << '\n';
        }
        // 도달할 수 있는 경우 거리를 출력
        else {
            cout << d[i] << '\n';
        }
    }
}

플로이드 워셜 알고리즘

 

 

 

내용 및 코드 참고

www.youtube.com/watch?v=acqm9mM1P6o&list=PLRx0vPvlEmdAghTr5mXQxGpHjWqSz0dgC&index=7