> For the complete documentation index, see [llms.txt](https://nelmm.gitbook.io/til/llms.txt). Markdown versions of documentation pages are available by appending `.md` to page URLs; this page is available as [Markdown](https://nelmm.gitbook.io/til/algorithm/dijkstra.md).

# Dijkstra's Algorithm

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

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

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

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

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

\ <br>

## 특징

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

\ <br>

## 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
```

\ <br>

## 구현 방법

<br>

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

<br>

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

<br>

### 인접 행렬

***

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

```cpp
    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]`추가 되었다.

```cpp
    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];
        }
    }
```

<br>

### 인접 리스트

***

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

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

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

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

```cpp
    /*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];
        }
    ㅋ}
```

\ <br>

## 시간 복잡도

<br>

`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)이기 때문이다.

\ <br>

## 구현 코드

<br>

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

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

```cpp
#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);
}
```