Dijkstra's Algorithm

그래프 중에서 최단 경로를 찾는 알고리즘중에 하나로 하나의 정점에서 다른 모든 정점까지의 최단경로를 구하는 알고리즘 (single-source shortest path algorithmm)

우선순위 큐의 방법을 이용하는 알고리즘이다.

vertex를 한개씩 선택하며 최단 경로를 찾는 방법.

relax의 개념을 이용하며 relax는 현재 계산된 v노드까지의 거리보다 현재 노드 u까지의 경로와 u에서 v의 가중치 ( e(u,v) ) 가 더 작다면 값을 갱신해주는 것.

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

특징

• 탐욕적인 방법( Greedy Method )

• 정점 선택 기반

• 음의 가중치 허용 x

• 시작 정점부터 출발하여 최소 비용의 간선을 갖는 정점을 선택하여 신장 트리 집합을 단계적으로 확장

• 밀집 그래프에 적합

• 자료구조중 하나인 우선순위 큐를 이용하며, 우선순위 큐를 어떻게 구현했는가가 시간복잡도에 영향

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

구현 방법

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가 선택되었다면 끝난다.

인접 행렬

---

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

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

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

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

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

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

인접 리스트

---

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

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

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

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

    /*select한 vertex와 인접한 간선인 e*/
    for (auto e : adjList[select_key]) {
        if (!selected[e.second] && 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];
        }
    ㅋ}

시간 복잡도

Prim's 알고리즘과 동일하다.

시간복잡도는 초기화하는데 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)이기 때문이다.

구현 코드

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

소스코드 c++ ( 접기 / 펼치기 )

#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값 계산
    std::vector<bool> selected(V, false);      //선택된 vertex인가

    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;
        selected[select_key] = true;
        std::cout << "dest : " << select_key << " (dis : " << vertex_key[select_key] << ")" << std::endl;

        /*decrease key*/
        for (auto e : adjList[select_key]) {
            if (!selected[e.second] && 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값 계산
    std::vector<bool> selected(V, false);      //선택된 vertex인가

    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 (!selected[j] && min_of_key > vertex_key[j]) {
                select_idx = j;
                min_of_key = vertex_key[j];
            }
        }

        sum += min_of_key;
        selected[select_idx] = true;

        std::cout << "dest : " << select_idx << " (dis : " << vertex_key[select_idx] << ")" << std::endl;

        /*decrease key*/
        for (int j = 0; j < V; j++) {
            if (!selected[j] && 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);
}