[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

JVM과 자바 실행

JVM과 자바 실행

  • Java
  • 2021년 1월 22일

백기선님의 유튜브 로 진행하시는 스터디를 진행하며 올리는 정리 블로그입니다. 1. JVM Java Virtual Machine의 약자로 Java와 OS사이에서 중개자 역할을 하여 메모리 관리, GC(garbage collection)을 수행하는 스택기반의 가상머신으로 C++,C와 같은 언어들과 다르게 OS에 상관없이 동작이 가능하다. Java는 C나 C++과 같이 바로 컴파일...

Read More
함수

함수

1. 함수 생성 방법 package main func main(){ a := 1 say(a) } func say(a int) { println(a) } func키워드를 이용해서 함수를 선언할 수 있고 가장 기본적으로 만드는 main도 함수 이다. 2. 매개변수(인자) 1) 전달 방식 Java처럼 primitive자료형은 pass by value, reference자료형은 pass by refernece가 아닌 go는 C처럼 *을 이용해서 value인지 refer...

Read More
[Disjoint Set] Union Find 알고리즘

[Disjoint Set] Union Find 알고리즘

1. Disjoint Set 번역하면 서로소 집합으로 서로 중복 되지 않는 부분 집합들로 이루어진 집합(set)으로 교집합이 존재 하지 않는 부분집합들로 이루어진 집합이다. 2. Union-Find Union : 두개의 집합을 하나의 집합으로 합치는 것. Find : 어떤 원소가 주어졌을 때 이 원소가 속한 집합을 반환하는(찾는) 것. 집합들을 tree구조로 나타내어 해당원소가 어떤 집합에 속하는지 판단...

Read More