기술면접 알고리즘 [Graph] : 다익스트라 (최단 경로)

기술면접과 코딩테스트 준비를 위해 꼭 알아야 할 기초 알고리즘 관련 개념들과 코드를 정리하고 있습니다.

각 주제들은 GeeksForGeeks 의 Top 10 algorithms in Interview Questions 글에서 발췌하였습니다.

---

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

다익스트라는 주어진 시작 지점에서 최단경로를 구하는 알고리즘으로, 양의 가중치 간선들로 이루어진 그래프일 경우에 한 지점에서 특정 지점까지의 최단경로를 구하는 알고리즘이다.

Naive 하게 모든 정점들을 체크하며, 거리값을 relaxation 해주는 경우 시간 복잡도는 O(V^2) 가 나온다. (dijkstra_slow 함수로 구현)

Priority_Queue 를 사용하여 최소 거리의 정점을 Heapify 해줄 경우, 시간 복잡도는 O( (V + E) * log(V) ) 가 나온다. (dijkstra 함수로 구현)

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


#define V           9
#define DIST_MAX    999999

typedef std::pair<int, int> myP;

struct compare {
    bool operator()(myP a, myP b) {
        return a.second > b.second;
    }
};

void dijkstra(int graph[V][V], int st) {

    std::cout << "Vertex\t" << "Distance from Source" << std::endl;

    for (int end = 0; end < V; ++end) {

        std::priority_queue<myP, std::vector<myP>, compare> q;
        int dist[V];
        for (int i = 0; i < V; ++i)
            dist[i] = DIST_MAX;

        dist[st] = 0;
        q.push(std::make_pair(st, dist[st]));

        std::pair<int, int> cur;
        while (!q.empty()) {
            cur = q.top();
            
            if (cur.first == end) {
                break;
            }
            q.pop();

            for (int i = 0; i < V; ++i) {
                if (graph[cur.first][i] > 0 && dist[i] > graph[cur.first][i] + cur.second) {
                    dist[i] = graph[cur.first][i] + cur.second;
                    q.push(std::make_pair(i, dist[i]));
                }
            }
        }

        std::cout << end << "\t\t\t\t" << dist[end] << std::endl;
    }
}

void dijkstra_slow(int graph[V][V], int st) {
    
    std::cout << "Vertex\t" << "Distance from Source" << std::endl;

    for (int end = 0; end < V; ++end) {

        int dist[V];
        for (int i = 0; i < V; ++i)
            dist[i] = DIST_MAX;

        dist[st] = 0;

        std::pair<int, int> cur;
        for (int i = 0; i < V; ++i) {
            for (int j = 0; j < V; ++j) {
                if (graph[i][j] > 0 && dist[j] > dist[i] + graph[i][j]) {
                    dist[j] = dist[i] + graph[i][j] ;
                }
            }
        }

        std::cout << end << "\t\t\t\t" << dist[end] << std::endl;

    }
}

// driver program to test above function
int main()
{
   
    /* Let us create the example graph discussed above */
    int graph[V][V] = { { 0, 4, 0, 0, 0, 0, 0, 8, 0 },
                        { 4, 0, 8, 0, 0, 0, 0, 11, 0 },
                        { 0, 8, 0, 7, 0, 4, 0, 0, 2 },
                        { 0, 0, 7, 0, 9, 14, 0, 0, 0 },
                        { 0, 0, 0, 9, 0, 10, 0, 0, 0 },
                        { 0, 0, 4, 14, 10, 0, 2, 0, 0 },
                        { 0, 0, 0, 0, 0, 2, 0, 1, 6 },
                        { 8, 11, 0, 0, 0, 0, 1, 0, 7 },
                        { 0, 0, 2, 0, 0, 0, 6, 7, 0 } };
 
    dijkstra(graph, 0);
    // dijkstra_slow(graph, 0); // O(V^2)
 
    return 0;
}