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

 

최단 거리 알고리즘에는 다익스트라 최단 경로 알고리즘, 플로이드 워셜, 벨만 포드 알고리즘 등이 있다. 이 중 다익스트라 최단 경로와 플로이드 워셜 알고리즘이 코딩 테스트에서 가장 많이 등장하는 유형이다. 또한 최단 경로 알고리즘은 그리디와 DP의 한 유형으로 볼 수 있다.

그럼 다익스트라 최단 경로와 와 플로이드 워셜 알고리즘을 알아보자.

 

 

---

 

 

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

다익스트라 최단 경로 알고리즘은 그래프에서 여러 개의 노드가 있을 때, 특정한 노드에서 출발해 다른 노드로 가는 각각의 최단 경로를 구해주는 알고리즘이다. 다익스트라 최단 경로 알고리즘은 '음의 간선'이 없을 때 정상적으로 동작하며, 실제로 GPS 소프트웨어의 기본 알고리즘으로 채택되곤 한다. 다익스트라 최단 경로 알고리즘은 다음과 같이 진행된다.

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

다익스트라 최단 경로 알고리즘에서는 방문하지 않은 노드 중에서 가장 최단 거리가 짧은 노드를 선택하는 과정을 반복하는데, 이렇게 선택된 노드는 '최단 거리'가 완전히 선택된 노드이므로, 더 이상 알고리즘을 반복도 최단 거리가 줄어들지 않는다. 다시 말해, 한 단계당 하나의 노드에 대한 최단 거리를 확실히 찾는 것으로 이해할 수 있다.

 

간단한 다익스트라 알고리즘

#include "iostream"
#include "vector"
#define INF 1e9

using namespace std;

int n, m, start;						// 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;
    }

    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;
        graph[a].push_back({b, c}); // a노드 -> b노드의 비용이 c
    }

    fill_n(d, 100001, INF);
    dijkstra(start);

    for (int i = 1; i <= n; i++) {
        if (d[i] == INF) cout << "INFINITY" << endl;
        else cout << d[i] << endl;
    }
}

위 코드는 간단한 다익스트라 최단 경로 알고리즘을 구현한 것이다.

이렇게 구현할 경우, 시간 복잡도는 O(V^2)이다. (V: 노드의 개수) 

따라서 전체 노드의 개수가 5,000개 이하라면 이 코드로 문제를 풀 수 있지만 , 노드의 개수가 10,000개를 넘어간다면 이 코드로는 문제를 해결하기 어렵다. 이런 경우에는 개선된 다익스트라 알고리즘을 이용해야 한다.

 

개선된 다익스트라 알고리즘

개선된 다익스트라 알고리즘에서는 힙 자료구조를 사용한다. 힙을 이용하게 되면 시작 노드로부터 가장 거리가 짧은 노드를 더욱 빠르게 찾을 수 있다. 따라서 시간 복잡도 O(ElogV)를 보장한다. (E: 간선의 개수, V: 노드의 개수)

#include "iostream"
#include "vector"
#include "queue"
#define INF 1e9

using namespace std;

int n, m, start;                        // n: 노드 개수, m: 간선 개수, start: 시작 노드
vector<pair<int, int>> graph[100001];   // 그래프 전체 정보 배열
int d[100001];                          // 최단 거리 테이블

void dijkstra(int start) {
    priority_queue<pair<int, int>> pq;
    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;
        graph[a].push_back({b, c}); // a노드 -> b노드의 비용이 c
    }

    fill(d, d + 100001, INF);
    dijkstra(start);

    for (int i = 1; i <= n; i++) {
        if (d[i] == INF) cout << "INFINITY" << endl;
        else cout << d[i] << endl;
    }
}

 

 

---

 

 

📌  플로이드 워셜 알고리즘

다익스트라 알고리즘은 '한 지점에서 다른 특정 지점까지의 최단 경로를 구해야 하는 경우'에 사용할 수 있는 최단 경로 알고리즘이다. 반면에 플로이드 워셜 알고리즘(Floyd-Warshall Algorithm)은 '모든 지점에서 다른 모든 지점까지의 최단 경로를 모두 구해야 하는 경우'에 사용할 수 있는 알고리즘이다. 

 

플로이드 워셜 알고리즘의 시간 복잡도는 O(N^3)인데, 노드의 개수가 N개일 때 2차원 리스트를 처리해야 하므로 N단계에서 매번 O(N*2)의 시간이 소요되기 때문이다. 또한 다익스트라 알고리즘은 그리디 알고리즘이지만, 플로이드 워셜 알고리즘은 N번 만큼의 단계를 반복하며 '점화식에 맞게' 2차원 리스트를 갱신하기 때문에 DP로 볼 수 있다.

 

각 단계에서는 해당 노드를 거쳐가는 경우를 고려한다. 예를 들어 1번 노드를 확인할 때에는 1번 노드를 중간에 거쳐가는 모든 경우를 고려하면 된다. A -> 1번 노드 -> B로 가는 비용을 확인한 후에 최단 거리를 갱신하는 형태이다. 따라서 현재 확인하고 있는 노드를 제외하고, N -1 개의 노드 중에서 서로 다른 노드 (A, B)쌍을 선택해 비용을 확인한 후 최단 거리를 갱신하는 작업을 반복한다. 

#include "iostream"
#define INF 1e9

using namespace std;

int n, m;
int graph[501][501];

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

    // 최단 거리 테이블 초기화
    for (int i = 0; i < 501; i++) {
        fill(graph[i], graph[i] + 501, INF);
    }

    // 자기 자신 -> 자기 자신 비용 0으로 초기화
    for (int i  = 0; i <= n; i++) {
        for (int j = 0; j <= n; j++) {
            if (i == j) graph[i][j] = 0;
        }
    }

    // 간선 정보 저장
    for (int i = 0; i < m; i++) {
        int a, b, c;
        cin >> a >> b >> c;
        graph[a][b] = c;
    }

    // 플로이드 워셜 알고리즘 수행
    for (int k = 1; k <= n; k++) {
        for (int a = 1; a <= n; a++) {
            for (int b = 1; b <= n; b++) {
                graph[a][b] = min(graph[a][b], graph[a][k] + graph[k][b]);
            }
        }
    }

    // 결과 출력
    for (int i = 1; i <= n; i++) {
        for (int j = 1; j <= n; j++) {
            if (graph[i][j] == INF) cout << "INFINITY" << " ";
            else cout << graph[i][j] << " ";
        }
        cout << endl;
    }
}

 

 

 

🔗  참고 자료

이것이 취업을 위한 코딩 테스트다 with 파이썬 : 네이버 도서