다익스트라(Dijkstra Algorithm)

1. 알고리즘

G : 그래프를 나타내는 인접리스트, 인접행렬
S : 출발점
Distance 배열 : 거리를 저장할 배열

<추가적으로 우선순위 큐와 방문정보를 저장하는 배열을 사용하면 더 적은 공간/시간 복잡도를 얻을 수 있다.>

<prev라는 이전 노드를 저장하는 배열을 통해, 경로를 구할 수 있다.>

 

(1) distance[출발점] = 0, 나머지를 INF로 설정한다. 

(2) 현재 점에 직접 연결된 정점들의 distance 배열에서의 값과 현재점을 지나간 경로의 대소를 비교하여, 적은 쪽을 선택하여 distance 배열에 저장한다..

   distance[target] > distance[now] + G[now->target]

(3) 현재 방문하지 않은 노드 중, distance가 가장 작은 점을 방문한다.(현재점으로 설정)

- 이때, 우선순위 큐를 사용하면 가장 작은 점을 찾는 알고리즘을 log의 시간복잡도로 줄일 수 있다.

(4) 2,3을 모든 정점을 방문할 경우까지 수행한다.

 

다익스트라
  #모두 방문하기 전까지
  while !all visit : 
    #현재 distance 배열에서 방문하지 않은 배열 중 가장 가까운 노드
    now <- minimum distance point of unvisited point
    #해당 노드 방문 체크
    visit now = true
    #해당 노드에서 갈 수 있는 모든 점 i
    for i in G[now -> i]:
      #i의 현재 측정된 거리보다 now를 거쳐서 i를 가는 것이 빠르다면 갱신
      if distance[i] > distance[now] + G[now -> i] :
      	distance[i] = distance[now] + G[now -> i]

*위 코드는 스도코드입니다.

다익스트라
  #모두 방문하기 전까지
  while queue empty : 
    #현재 distance 배열에서 방문하지 않은 배열 중 가장 가까운 노드
    now <- 우선순위 큐 pop
    # 이미 방문한 노드라면
    if visit now is true : continue
    #해당 노드 방문 체크
    visit now = true
    #해당 노드에서 갈 수 있는 모든 점 i
    for i in G[now -> i]:
      #i의 현재 측정된 거리보다 now를 거쳐서 i를 가는 것이 빠르다면 갱신
      if distance[i] > distance[now] + G[now -> i] :
      	distance[i] = distance[now] + G[now -> i]
        # 큐에 방문할 수 있는 후보 넣기
        queue push (distance, i)

* 우선순위 큐 사용(스도코드 입니다.)

 

2. 시간복잡도

다익스트라에서 시간복잡도는 

 

우선순위 큐를 사용하지 않는 경우(with 인접행렬)

모든정점 V개를 방문할 때까지, V개의 배열에서 최솟값을 찾아야 하므로,

$V^2$

이고, 총 E(모든 간선)을 탐색하기 때문에

$V^2 + E$

이다. 일반적으로 V^2 > E 이므로

$O(V^2)$

이다.

 

우선순위 큐를 사용하는 경우

우선순위 큐에 insert와 delete의 시간복잡도는 logV이다.

우선순위 큐에 insert는 간선의 개수(E) 회,

우선순위 큐에 delete는 정점의 개수(V) 회를 수행한다.

$O((V+E)logV)$

 

 

3. 응용

다익스트라 문항에서 흔히 나오는 응용 문제 풀이는 다음과 같다.

1. x에서 y로 가는 최소가 아닌 모든 정점에서 y로 가는 최소 구하기.

BOJ1238문항 www.acmicpc.net/problem/1238

1238번: 파티

#include <iostream>
#include <vector>
#include <algorithm>
#include <queue>
#include <climits>
#define p pair<int, int>

using namespace std;

vector<p> v1[1005],v2[1005];
int dp[1005], dp2[1005];
bool visited[1005];

int main(){
    ios_base::sync_with_stdio(false),cin.tie(nullptr),cout.tie(nullptr);
    int n, m, x;
    cin >> n >> m >> x;
/* 
    입력받기
    v1 <- 정방향 저장 : x에서 돌아가는 길을 계산하기 위해
    v2 <- 역방향 저장 : x로 들어오는 길을 계산하기 위해
*/
    for(int i = 0; i < m;i++){
        int s,e,v;
        cin >> s >> e >> v;
        //v1에는 방향에 맞는 칸
        v1[s].push_back({v,e});
        //v2에는 역방향
        v2[e].push_back({v,s});
    }
    fill_n(dp, 1005, INT_MAX);
    fill_n(dp2, 1005, INT_MAX);
    fill_n(visited, 1005, false);


/*
    다익스트라1 : x 에서 돌아가는 소요시각을 계산
*/
    priority_queue<p, vector<p>, greater<p>> pq;
    pq.push({0, x});
    dp[x] = 0;
    while(!pq.empty()){
        p t = pq.top();
        pq.pop();
        if(visited[t.second])   continue;
        visited[t.second] = true;
        for(auto neighbor : v1[t.second]){
            if(dp[neighbor.second] > dp[t.second] + neighbor.first){
                dp[neighbor.second] = dp[t.second] + neighbor.first;
                pq.push({dp[neighbor.second], neighbor.second});
            }
        }
    }


/*
    초기화
    1. 방문 배열 초기화
    2. 우선순위 큐에 시작점 추가
    3. 시작점의 거리 0으로 초기화
*/
    fill_n(visited, 1005, false);
    pq.push({0, x});
    dp2[x] = 0;

/*
    다익스트라 2 : x로 들어오는 소요 시각을 계산
*/
    while(!pq.empty()){
        p t = pq.top();
        pq.pop();
        if(visited[t.second])   continue;
        visited[t.second] = true;
        for(auto neighbor : v2[t.second]){
            if(dp2[neighbor.second] > dp2[t.second] + neighbor.first){
                dp2[neighbor.second] = dp2[t.second] + neighbor.first;
                pq.push({dp2[neighbor.second], neighbor.second});
            }
        }
    }

    for(int i = 1; i <= n; i++){
        dp[i] = dp[i] + dp2[i];
    }

    cout << *max_element(dp + 1, dp + n + 1);
}

 

2. 최단 경로 출력

추후 추가 예정

 

3. 그래프 만들기

추후 추가 예정