[SPSP] Dijkstra 알고리즘

그래프 중에서 최단 경로를 찾는 알고리즘중에 하나로 하나의 정점에서 다른 모든 정점까지의 최단경로를 구하는 알고리즘 (single-source shortest path algorithmm)으로 우선순위 큐의 방법을 이용하는 알고리즘이다.

가장 최적의 vertex를 한개씩 선택하며 최단 경로를 찾는 방법으로 relax의 개념을 이용하며 relax는 현재 계산된 v노드까지의 거리보다 현재 노드 u까지의 경로와 u에서 v의 가중치 ( e(u,v) ) 가 더 작다면 값을 갱신해준다.

이때, relax는 prim 알고리즘의 decrease-key와 유사하며 dp를 추가한 개념이다.


1. 특징

  • 음의 가중치 허용 x
  • 시작 정점부터 출발하여 최소 비용의 간선을 갖는 정점을 선택하여 신장 트리 집합을 단계적으로 확장
  • 밀집 그래프에 적합
  • 자료구조중 하나인 우선순위 큐를 이용하며, 우선순위 큐를 어떻게 구현했는가가 시간복잡도에 영향

2. Pesudo Code

Dijkstra(G, w , s){
    INITIALIZE-SINGLE-SOURCE(G, s)
    S <- ∅ Q <- V[G]
    while Q != ∅
        do u <- EXTRACT-MIN(∅)
        s <- S ∪ {u}
        for each vertex v ∈ Adj[u]
            do RELAX(u, v, w)
}

RELAX(u,v,w)
    if v.d > u.d + w(u,v)
        v.d = u.d + w(u,v)
        v.π = u

3. 구현 방법

Prim’s 알고리즘에서 decrease key 부분을 dp를 이용한다는 것 빼고 다른 것이 없다.

  1. vertex들의 key값을 Infinity로 초기화
  2. start vertex의 key값을 0으로 초기화 (어떤 vertex를 선택하더라고 MST가 나온다.)
  3. 현재 vertex에 인접한 vertex들 중 선택하지 않았고, 가장 vertex의 key값이 작은 vertex을 찾기 (exract-min = 최소값 추출)
  4. 현재 vertex를 선택
  5. 인접한 vertex중 vertex의 key값보다 간선의 가중치와 현재까지의 거리의 합이 더 작다면 key값을 가중치와 현재까지의 거리의 합으로 갱신 (RELAX)
  6. 인접한 vertex중 선택하지 않았고, 가장 vertex의 key값이 작은 vertex를 기준으로 3번부터 다시 반복
  7. 모든 vertex가 선택되었다면 종료

1) 인접 행렬

위에 설명한 3번 방법의 extract-min을 아래와 같이 배열로 구현하며, 매번 V회 반복한다.

int v = -1;              //인접 vertex중 가장 작은 가중치를 갖는 vertex
int min_key = INFINITY;  //인접 vertex중 가장 작은 가중치

/* 인접 vertex중 가장 작은 가중치를 갖는 vertex 찾기*/
for (int j = 0; j < V; j++) {
  if (min_key > vertex_key[j]) {
    v = j;
    min_key = vertex_key[j];
  }
}

아래는 5번 방법으로 인접한 vertex중 vertex의 key값보다 간선의 가중치와 현재까지의 거리의 합이 더 작다면 key값을 가중치와 현재까지의 거리의 합으로 갱신 한다..

잘 보면 알겠지만 Prim 알고리즘과 비교해서 vertex_key[selct_idx] 추가 됐다.

for (int j = 0; j < V; j++) {
  if ( vertex_key[j] > adjMatrix[select_idx][j] + vertex_key[select_idx]) {
    vertex_key[j] = adjMatrix[select_idx][j] + vertex_key[select_idx];
  }
}

2) 인접 리스트

인접 리스트는 인접한 vertex의 가중치를 priority queue를 통해 저장한다.

때문에, 3번 방법의 exract-min은 맨앞에서 pop을 시켜 찾아주면 된다.

int select_key = q.begin()->second;
int min_of_key = q.begin()->first;
q.erase(q.begin());

    /*select한 vertex와 인접한 간선인 e*/
for (auto e : adjList[select_key]) {
  if ( vertex_key[e.second] > e.first + vertex_key[select_key]) {
    q.erase({vertex_key[e.second], e.second});  //같은 노드로 향하는 간선중 weight가 더 작은 간선이 있다면 그 전 간선은 삭제
    q.insert({e.first, e.second});  //큐에 삽입
    vertex_key[e.second] = e.first + vertex_key[select_key];
  }
}

5번 방법으로 인접한 vertex중 vertex의 key값보다 간선의 가중치와 현재 정점까지의 거리의 합이 더 작다면 key값을 가중치와 현재 정점까지의 거리의 합으로 갱신 하는 방법은 아래와 같이 인접한 간선의 개수만큼 수행한다.


4. 시간 복잡도

Prim 알고리즘과 거의 동일하기 때문에 시간복잡도도 동일하다.

시간복잡도는 초기화하는데 O(|V|), MST계산하는데 O(|V|) * T(extract-min) (가장 적은 값 추출하는데 걸린시간) + O(|E|) * T(RELAX) ( key값 변경하는데 걸리는 시간 )와 같기 때문에 priority-queue를 어떻게 구현했는지에 따라 시간복잡도가 달라진다.

일반 배열로 구현했을 경우 T(extract)가 O(|V|), T(RELAX)는 O(1) 만큼 걸려 총 O(|V^2|) 이 걸린다.

binary heap(이진 힙)으로 구현하면 T(extract)가 O(lgV), T(RELAX)는 O(lgV) 만큼 걸려 총 O(VlgV) + O(ElgV) 이기 때문에 O((E+V)lgV) 만큼 걸린다.
무방향 그래프일때 E의 최소값은 V-1로 거의 대부분이 |E| > |V| 이므로 O(|E|lg|V|) 라고 할 수 있다.

priority queue를 이진 힙이 아닌 fibonacci heap으로 구현하면 RELAX의 시간을 좀더 줄일 수 있는데 RELAX시간이 O(1) 만큼 걸리기 때문에 O(E+VlgV) 라고 할 수 있다.
O(E) or O(VlgV) 인 이유는 최악의 경우에 E는 O(V^2)이기 때문이다.


구현 코드

아래 코드는 사이클이없는 무방향의 그래프이고, 가중치를 무작위로 생성한 그래프이다.

#include <time.h>  //시간 측정

#include <algorithm>  //for_each
#include <cstdlib>    //rand
#include <ctime>      //time
#include <iostream>
#include <set>
#include <vector>

#define INFINITY 2147483647
#define II std::pair<int, int>  // first = weight, second = dest

typedef struct edge {
    int src;     //출발 vertex
    int dest;    //도착 vertex
    int weight;  //가중치(비용)
} edge;

class Graph {
   private:
    edge e;

   public:
    Graph(int src = 0, int dest = 0, int weight = 0) {
        this->e.src = src;
        this->e.dest = dest;
        this->e.weight = weight;
    }
    int getSrc() { return this->e.src; }
    int getDest() { return this->e.dest; }
    int getWeight() { return this->e.weight; }
};

void CalcTime();
void randomPush(std::vector<Graph> &);     // graph에 사이클 없는 연결그래프 cost값 무작위 생성
void print_edge_info(std::vector<Graph>);  // graph 간선들 보기
void make_adj_list(std::vector<Graph>, std::vector<std::vector<II>> &);     //주어진 그래프를 인접리스트로 표현
void make_adj_matrix(std::vector<Graph>, std::vector<std::vector<int>> &);  //주어진 그래프를 인접행려로 표현

int dijkstra_heap(std::vector<Graph> &, std::vector<std::vector<II>>, int);
int dijkstra_array(std::vector<Graph> &, std::vector<std::vector<int>>, int);

int V;                                 // vertex 개수
clock_t start, finish, used_time = 0;  //실행 시간 측정을 위한 변수

int main() {
    std::vector<Graph> g;    // graph g
    int minimum_weight = 0;  // minimum cost
    std::vector<std::vector<int>> adjMatrix;
    std::vector<std::vector<II>> adjList;

    randomPush(g);  //간선 random 삽입
    // 10print_edge_info(g);  // edge info print

    make_adj_matrix(g, adjMatrix);  //주어진 그래프를 인접행렬로 만들기
    make_adj_list(g, adjList);      //주어진 그래프를 인접리스트로 만들기

    start = clock();
    // minimum_weight = dijkstra_heap(g, adjList, 0); //binary heap을 이용한 구현
    minimum_weight = dijkstra_array(g, adjMatrix, 0);  // array 이용한 구현
    finish = clock();
    std::cout << "\nall route dis : " << minimum_weight << std::endl;
    CalcTime();

    return 0;
}

int dijkstra_heap(std::vector<Graph> &g, std::vector<std::vector<II>> adjList, int start) {
    int sum = 0;
    std::set<II> q;                            //이진힙으로 queue 만들기 ( set은 red-black tree로 만들어짐 )
    std::vector<int> vertex_key(V, INFINITY);  // vertex의 최소 weight값 계산

    vertex_key[start] = 0;
    q.insert(II(0, start));  //시작 노드 가중치 0으로 시작
    std::cout << "\nstart : 0\n";

    /*Vertex만큼 반복*/
    while (!q.empty()) {
        /*extract min*/
        int select_key = q.begin()->second;
        int min_of_key = q.begin()->first;
        q.erase(q.begin());

        sum += min_of_key;
        std::cout << "dest : " << select_key << " (dis : " << vertex_key[select_key] << ")" << std::endl;

        /*decrease key*/
        for (auto e : adjList[select_key]) {
            if ( vertex_key[e.second] > e.first + vertex_key[select_key]) {
                q.erase({vertex_key[e.second], e.second});  //같은 노드로 향하는 간선중 weight가 더 작은 간선이 있다면 그 전 간선은 삭제
                q.insert({e.first, e.second});  //큐에 삽입
                vertex_key[e.second] = e.first + vertex_key[select_key];
            }
        }
    }
    std::cout << std::endl;
    return sum;
}

int dijkstra_array(std::vector<Graph> &g, std::vector<std::vector<int>> adjMatrix, int start) {
    int sum = 0;
    std::vector<int> vertex_key(V, INFINITY);  // vertex의 최소 weight값 계산

    vertex_key[start] = 0;
    std::cout << "\nstart : 0\n";

    /*Vertex만큼 반복*/
    for (int i = 0; i < V; i++) {
        /*extract min*/
        int select_idx = -1, min_of_key = INFINITY;
        for (int j = 0; j < V; j++) {
            if (min_of_key > vertex_key[j]) {
                min_of_key = vertex_key[j];
            }
        }

        sum += min_of_key;
        std::cout << "dest : " << select_idx << " (dis : " << vertex_key[select_idx] << ")" << std::endl;

        /*decrease key*/
        for (int j = 0; j < V; j++) {
            if ( vertex_key[j] > adjMatrix[select_idx][j] + vertex_key[select_idx]) {
                vertex_key[j] = adjMatrix[select_idx][j] + vertex_key[select_idx];
            }
        }
    }
    std::cout << std::endl;
    return sum;
}

void make_adj_list(std::vector<Graph> g, std::vector<std::vector<II>> &adj) {
    adj.resize(V);
    bool isEdge;
    for (int i = 0; i < g.size(); i++) {
        isEdge = false;
        int src = g[i].getSrc();
        int dest = g[i].getDest();
        int weight = g[i].getWeight();

        /*동일 vertex로 향하는 간선중 가장 작은 값만가지고 인접 리스트를 만들기 위한 코드*/
        if (adj[src].empty()) {
            adj[src].push_back({weight, dest});
        } else {
            for (int j = 0; j < adj[src].size(); j++) {
                if (adj[src][j].second == dest) {
                    isEdge = true;
                    if (adj[src][j].first > weight) {
                        adj[src][j].first = weight;
                    }
                }
            }
            if (!isEdge) adj[src].push_back({weight, dest});
        }
    }
}

void make_adj_matrix(std::vector<Graph> g, std::vector<std::vector<int>> &adj) {
    adj.assign(V, std::vector<int>(V, INFINITY));
    for (int i = 0; i < g.size(); i++) {
        int src = g[i].getSrc();
        int dest = g[i].getDest();
        int weight = g[i].getWeight();

        if (adj[src][dest] > weight) {
            adj[src][dest] = weight;
        }
    }
}

/*vertex수 입력받은 후 그래프 간선 가중치 random 삽입*/
void randomPush(std::vector<Graph> &g) {
    std::cout << "create number of Vertex : ";
    std::cin >> V;

    srand((unsigned int)time(NULL));
    for (int i = 0; i < V - 1; i++) {
        g.push_back(Graph(i, i + 1, rand() % 1000));
        for (int j = i + 1; j < V; j++) {
            g.push_back(Graph(i, j, rand() % 1000));
        }
    }
    for (int i = (rand() % 3); i < V - 1; i += (rand() % 10)) {
        g.push_back(Graph(i, i + 1, rand() % 1000));
        for (int j = i + 1; j < V; j += (rand() % 10)) {
            g.push_back(Graph(i, j, rand() % 1000));
        }
    }
}

void print_edge_info(std::vector<Graph> g) {
    std::cout << "edge info : \n";
    std::for_each(g.begin(), g.end(), [](Graph a) {
        std::cout << "src : " << a.getSrc() << " desc : " << a.getDest() << " weight : " << a.getWeight() << std::endl;
    });
}

//실행 시간을 측정 및 출력하는 함수
void CalcTime() {
    used_time = finish - start;
    printf("\n*********** result **********\n     time : %lf sec\n", (double)(used_time) / CLOCKS_PER_SEC);
}
Tags :

Related Posts

상수

상수

상수는 Immutable(불변)한 특징을 갖으며 한 번 할당된 값을 변경할 수 없는 변수이다. 상수 키워드는 const로 선언방식은 변수 var와 같고 short assginment statement는 var키워드 전용이기 때문에 상수는 짧은 대입문 사용이 불가능 하다. 또한, 반드시 컴파일 타임에 실행이 가능한 표현식이어야만 한다....

Read More
GraphQL 서버 구축하기

GraphQL 서버 구축하기

이번에 버스 공공api를 이용해 현재 gps를 기반으로한 승차 예약 시스템 프로젝트를 진행중에 있는데, 이때의 구축과정기를 작성하려고 한다. 1. Spring boot에 GraphQL적용 이유 우선, nodeJS를 이용하면 조금 더 편하게 구현할 수 있었을 텐데 그것이 아닌 Spring boot를 이용해서 GraphQL을 사용하는 이유가 프로젝트를 진행하면서 처음 팀원간 합의 할때는 Rest하게 만들 생각이었고, nodeJS는 사용을 저만 해보았기 때문에 Spring boot로 처음 프로젝트를 시작 했다....

Read More
가상면접 사례로 배우는 대규모 설계 기초

가상면접 사례로 배우는 대규모 설계 기초

  • Books
  • 2022년 3월 23일

나는 얇은 책이거나 꼭 소장할 책이 아니라면 주로 알라딘 에서 ebook으로 책을 구매해서 읽는다.(전공 서적은 주로 너무 두꺼워 집에 둘 곳이 없다&hellip;) 책을 구매한 날도 알라딘에 어떤 ebook이 등록되었나 보고 있었고, 이 책의 제목이 굉장히 흥미를 끌었고 바로 구매를 해버렸다. 처음 구매후, 11장 까지는 굉장히 재미있게 읽어가다가 점점 루즈해져갔고, 읽는것을 한동안 중단했었다. 업무가 바쁘기도 했고 다른 DDD책이 더 재미가 있었다.. 그러다가 최근 부터 이직준비를 조금씩 하고 있었는데, 이 때문인지 책을 다시 읽기 시작했고 11장 부터 끝까지 한번에 다 본 것 같다....

Read More