[알고리즘] 최단거리 알고리즘(Dijkstra,Floyd Warshall)

Dijkstra Algorithm

다익스트라 알고리즘은 하나의 정점에서 다른 모든 정점으로 가는 최단 거리를 구하는 알고리즘 입니다. A,B,C,D,E,F 노드가 있을 때 하나의 정점A를 기준으로 A-B, A-C, A-E ...까지의 최단거리를 구할 수 있습니다. 이전에 구한 값을 재사용한다는 의미에서 다이나믹프로그래밍, 항상 가장 짧은 거리의 노드를 선택한다는 점에서 그리디 알고리즘으로 분류하기도 합니다.

 

1. 출발 노드를 설정

2. 출발 노드를 기준으로 각 노드의 거리를 저장

3. 방문하지 않은 노드 중에서 가장 거리가 짧은 노드를 선택

4. 해당 노드를 거쳐가는 경우와 거쳐가지 않은 경우를 비교하여 최단거리 갱신

5. 3,4 과정을 반복

 

A를 기준으로 각 노드의 거리 저장하였습니다. D,E의 경우 현재 직접적으로 연결되지 않았기 때문에 INF로 표시해두었습니다.

 

 방문하지 않은 노드 중에서 가장 거리가 짧은 노드를 선택합니다. B의 경우 거리가 4이고, C의 경우 거리가 1이기 때문에 C를 선택합니다. 그러면 이제 A에서 바로 가는 경우와 C를 거쳐서가는 거리을 비교해봅니다. 그리고 이미 거쳐간 노드는 다시 거쳐갈 일이 없이 때문에 체크를 해줍니다.

 

A-> B : A -> B바로 가는 경우 거리가 4이지만 A->C->B의 경우 거리가 3이 됩니다.

A-> D : A-> D의 경우 INF이지만 A->C->D의 경우 거리가 5이 됩니다.

A -> E : A-> E의 경우 INF이지만 A->C->D의 경우 거리가 6이 됩니다.

 

그 다음으로 방문하지 않은 노드 중에서 가장 거리가 짧은 노드는 B입니다. 이제 A에서 다른 모든 정점을 가는 경우와 B를 거쳐서 가는 경우의 거리를 비교해 보겠습니다.

 

A-> D : A-> D의 경우 이미 C를 거쳐서 가는 경우에서 최단거리가 갱신되었습니다.

A -> E : A-> E의 경우 이미 C를 거쳐서 가는 경우에서 최단거리가 갱신되었습니다.

 

......

 

D,E의 경우 위의 과정과 똑같이 진행하면 아래의 결과가 나옵니다. 이렇게 A에서 B,C,D,E로 가는 최단경로는 3,1,5,6을 구할 수 있습니다. 

 

#include <iostream>

using namespace std;

int number = 6;
int INF = 1000000000;

int a[6][6] = {
    {0, 2, 5, 1, INF, INF},
    {2, 0, 3, 2, INF, INF},
    {5, 3, 0, 3, 1, 5},
    {1, 2, 3, 0, 1, INF},
    {INF, INF, 1, 1, 0, 2},
    {INF, INF, 5, INF, 2, 0},
};

bool v[6]; // 방문한 노드 체크
int d[6];  // 거리

int getSmallInddex()
{
    int min = INF;
    int index = 0;

    for (int i = 0; i < number; i++)
    {
        if (d[i] < min && !v[i])
        {
            min = d[i];
            index = i;
        }
    }

    return index;
}

void dijkstra(int start)
{
    for (int i = 0; i < number; i++)
    {
        d[i] = a[start][i];
    }

    v[start] = true;
    for (int i = 0; i < number - 2; i++)
    {
        int current = getSmallInddex();
        v[current] = true;
        for (int j = 0; j < 6; j++)
        {
            if (!v[j])
            {
                if (d[current] + a[current][j] < d[j])
                {
                    d[j] = d[current] + a[current][j];
                }
            }
        }
    }
}

int main()
{
    dijkstra(0);

    for (int i = 0; i < number; i++)
    {
        cout << d[i] << " "; // 0 2 3 1 2 4 
    }
    cout << endl;
    return 0;
}

위의 방식은 최단거리를 선형탐색으로 구한 경우이며 시간복잡도는 O(N^2)가 됩니다. 하지만 이런 경우 간선의 개수는 적은데 노드의 개수가 많다면 비효율적일 수 있습니다. 그렇기 때문에 더 빠른 성능을 보장하기 위해 '힙'을 사용하게 되는데 이경우 시간복잡도는 O(NlogN)이 됩니다.

 

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

using namespace std;

int number = 6;
int INF = 1000000000;

vector<pair<int, int>> a[7]; // 간선의 정보
int d[7];                    // 최소 비용

void dijkstra(int start)
{
    d[start] = 0;
    priority_queue<pair<int, int>> pq;
    pq.push({start, 0});

    while (!pq.empty()) // 가까운 순서대로 처리
    {
        int current = pq.top().first;
        int distance = -pq.top().second; // 짧은 것이 먼저 오도록 음수화
        pq.pop();

        if (d[current] < distance) // 최단 거리가 아닌 경우 pass
        {
            continue;
        }

        for (int i = 0; i < a[current].size(); i++)
        {
            int next = a[current][i].first; // 선택된 노드의 인접 노드
            int nextDistance = distance + a[current][i].second; // 선택된 노드를 인접 노드로 거쳐서 가는 비용

            if (nextDistance < d[next]) // 기존의 최소 비용보다 더 저렴하다면 교체
            {
                d[next] = nextDistance;
                pq.push({next, -nextDistance});
            }
        }
    }
}

int main()
{
    for (int i = 1; i <= number; i++)
    {
        d[i] = INF;
    }

    a[1].push_back({2, 2});
    a[1].push_back({3, 5});
    a[1].push_back({4, 1});

    a[2].push_back({1, 2});
    a[2].push_back({3, 3});
    a[2].push_back({4, 2});

    a[3].push_back({1, 5});
    a[3].push_back({2, 3});
    a[3].push_back({4, 3});
    a[3].push_back({5, 1});
    a[3].push_back({6, 5});

    a[4].push_back({1, 1});
    a[4].push_back({2, 2});
    a[4].push_back({3, 3});
    a[4].push_back({5, 1});

    a[5].push_back({3, 1});
    a[5].push_back({4, 1});
    a[5].push_back({6, 2});

    a[6].push_back({3, 5});
    a[6].push_back({5, 2});

    dijkstra(1);

    for (int i = 1; i <= number; i++)
    {
        cout << d[i] << " "; // 0 2 3 1 2 4
    }
    cout << endl;
    return 0;
}

---

Floyd Warshall Algorithm

다익스트라 알고리즘의 경우 하나의 정점에서 모든 정점으로의 최단거리를 구하는 문제였다면 플로이드 와샬 문제는 '모든 정점에서 모든 정점으로의 최단거리'를 구하는 알고리즘 입니다. 

 

플로이드 알고리즘은 다익스트라 알고리즘에 비해 간단한데, 플로이드 와샬은 '거쳐가는 정점'을 기준으로 최단거리를 구합니다. 예를 들어 C노드를 기준으로 할 때 A -> B의 거리와 A -> C + C -> B의 거리중 최단거리를 A->B 거리로 갱신합니다.

 

#include <iostream>

using namespace std;

int number = 4;
int INF = 1000000000;

int a[4][4] = {{0, 5, INF, 8}, {7, 0, 9, INF}, {2, INF, 0, 4}, {INF, INF, 3, 0}};

void floydWarshall()
{
    int d[number][number];

    for (int i = 0; i < number; i++)
    {
        for (int j = 0; j < number; j++)
        {
            d[i][j] = a[i][j];
        }
    }

    for (int via = 0; via < number; via++)
    {
        for (int start = 0; start < number; start++)
        {
            for (int end = 0; end < number; end++)
            {
                if (d[start][via] + d[via][end] < d[start][end])
                {
                    d[start][end] = d[start][via] + d[via][end];
                }
            }
        }
    }

    for (int i = 0; i < number; i++)
    {
        for (int j = 0; j < number; j++)
        {
            cout << d[i][j] << " ";
        }
        cout << "\n";
    }

    // 0 5 11 8
    // 7 0 9 13
    // 2 7 0 4
    // 5 10 3 0
}

int main()
{
    floydWarshall();
    return 0;
}