8주차 자료구조 스터디 - 다익스트라 알고리즘

1 ) 다익스트라란 ? 

: 음의 가중치가 없는 그래프의 한 정점에서 모든 정점까지의 최단 거리를 구하는 알고리즘 

• 그래프의 방향 유무는 상관없다 
• 간선 중 하나라도 가중치가 음수라면 사용할 수 없다. 이런 경우는 벨만포드를 사용한다. 
• 플로이드 와샬은 모든 정점에서 모든정점까지의 최단 거리를 구하지만 , 다익스트라는 한 정점에서부터 모든 저점까지의 최단 거리를 구하는 알고리즘이다. 
• 다익스트라가 DP문제인 이유는 최단 거리는 여러개의 최단 거리로 이루어져있기때문이다.
  코드를 보면 한 점까지의 최단거리를 구할 때 이전까지의 최단거리로 사용하는걸 확인할 수 있다.  

✨최단 거리를 구하는 알고리즘이 꽤 많다. 각 알고리즘마다의 어떤 점이 다른 지를 기억하고 있어야한다. 

 

2 )  다익스트라 알고리즘의 원리

• 리스트로 단순구현하는 법과 우선순위 큐를 이용하는 방법이 있다.
  구현은 우선순위 큐로 할 거지만, 이전에 리스트로 구현하는 방법에 대해서 이해해야한다. 

[리스트 구현 ]

1.  시작 노드의 cost 값을 0 , 다른 노드의 cost 값은 inf 설정해준다.  
2.  시작노드와 연결되어있는 노드들(도착노드)에 대해서 cost비용을 계산해줍니다.
   도착노드의 cost 은 기존 도착노드의 cost  vs 시작노드까지의 cost + 시작노드~도착노드의 가중치 중
   더 작은 것이다.
3.  시작노드와 연결되어있는 노드들에 대한 cost비용 계산이 끝났다면 시작노드를 방문처리해준다. 
4.  방문하지 않은 노드중에서 출발거리로부터의 cost가 가장 적은 노드를 선택한다. 2~4번 과정을 반복한다.
5. 모든 노드들이 "방문완료"상태거나, 혹은 더 이상 연결된 간선이 있어 더 이상 선택할 수 없다면 끝난다. 

리스트로 위와 같이 1 ~ 6 과정을 반복할 경우 4번 과정에서 시간이 오래 걸린다. 

cost가 가장 적은 노드를 구하기 위해 모든 노드를 한번 훑어줘야하기 때문이다.

이걸 우선순위큐가 해결해줄 수 있다. 

우선순위 큐에 cost 비용과 노드를 같이 넣어주면, 가장 적은 cost를 가지는 노드가 나오기 때문이다. 

 

[우선순위 큐 구현]

1.  시작 노드의 cost 값을 0 , 다른 노드의 cost 값은 inf 설정해준다.  
2.  시작노드와 연결되어있는 노드들(도착노드)에 대해서 cost비용을 계산해줍니다.
   도착노드의 cost 은 기존 도착노드의 cost  vs 시작노드까지의 cost + 시작노드~도착노드의 가중치 중 
   더 작은 것이다.
3.  cost 비용 계산이 끝났다면 우선순위 큐에 (노드, cost)를 같이 넣어준다. 
4.  시작노드를 방문처리해준다. 
5.  우선순위 큐를 거리에 대해 최소힙(그래야 최소거리가 나옴)으로 적용하여 top에 위치한 노드로 이동한다.
6. 모든 노드들이 "방문완료"상태거나, 혹은 더 이상 연결된 간선이 있어 더 이상 선택할 수 없다면 끝난다. 
   모든 노드들이 방문완료가 되었는지 매번 확인을 하면 시간이 걸리니 그냥 우선순위큐가 빌 때까지 반복

 

1 ) cost를 초기화해준다. 

현재 진입노드를 1로 두었으므로 1에 해당하는 A의 cost는 0, 나머지는 inf 로 설정해준다. 

 

2 ) 시작노드 a와 연결된 노드 b,c,d의 노드들의 cost를 계산한다. 

도착노드를 b라고 했을 때, b의 cost는 원래 b의 cost 비용과 a의 cost 비용 + a-b가중치 중 더 작은 값이다. 

원래 cost 비용이 inf였으므로 a의 cost비용 + 가중치 = 0 + 10으로 업데이트된다. 

c,d도 동일하다. 

 

3)  이후 우선순위 큐에 노드와 cost를 넣어준다.

c,d도 동일하다. 

 

4) 시작노드 a를 방문처리해준다. 

1 ) 우선순위 큐의 top에 위치한 노드인 b를 시작노드로 잡는다. 

b와 연결된 노드는 e로, e의 cost비용을 계산해준다. 

원래 e의 cost 비용인 inf 보다 시작노드인 b의 cost 비용 + b-e의 가중치비용이 더 작기때문에 업데이트된다.

업데이트 이후 노드 b는 방문처리 되고, 새롭게 계산된 e의 노드와 cost는 우선순위 큐에 넣어준다. 

 

2) 그 다음 우선순위 큐의 top에 위치한 노드인 d를 시작노드로 잡는다. 

 

d와 연결된 노드는 c,e로 c의 cost 비용부터 계산해보자. 

c의 원래 cost  : 30 , 시작노드인 d의 cost + d-c의 가중치 = 15 + 3 = 18이므로 업데이트 된다. 

새롭게 업데이트 됐으므로, 우선순위 큐에 c의 노드와 cost를 넣어준다. 

 

e의 원래 cost : 30 , 시작노드인 d의 cost + d-e의 가중치 = 15 + 5 = 20이므로 업데이트된다. 

e도 새롭게 업데이트 됐으므로, 우선순위 큐에 e의 노드와 cost를 우선순위 넣어준다. 

 

연결된 노드들에 대한 계산이 끝났으므로 d도 방문처리 해준다. 

 

3) 그 다음 우선순위 큐의 top에 위치한 노드인 c를 시작노드로 잡는다. 

c와 연결된 노드는 e 하나뿐이다. 

e의 원래 cost 비용은 20 이고, 시작노드인 c의 cost 비용 + c-e의 가중치 = 18 + 6 이므로 업데이트가 일어나지 않는다. 

연결된 노드들에 대해 계산이 끝났으므로 c도 방문처리해준다. 

 

4) 그 다음 우선순위 큐의 top에 위치한 노드인 e를 시작노드로 잡는다. 

e와 연결된 노드는 d 하나 뿐이다. 

d의 원래 cost 비용은 15 이고, 시작노드인 e의 cost 비용 + e-d의 가중치 = 20 + 20 이므로 업데이트가 일어나지 않는다. 

연결된 노드들에 대해 계산이 끝났으므로 e도 방문처리해준다. 

 

3) 시간복잡도 

리스트로 구현 :  $O(V^{2})$

우선순위 큐로 구현 : $O(E log V)$

 

4) 코드구현 

예제로 백준 1753번 최단경로 (www.acmicpc.net/problem/1753)

#include <iostream>
#include <vector>
#include<algorithm>
#include<queue>

using namespace std;

priority_queue<pair<int, int>, vector<pair<int, int>>, greater<pair<int, int>>>q; //거리 , 인덱스
vector<vector<pair<int, int>>> graph;
int cost[20005] = { 0 };
bool visited[20005] = { false };
int n, m; // 정점의 개수 , 입력의 개수 

void dijkstra(int start) {
    q.push({ 0 , start });
    visited[start] = true;

    while (!q.empty()) {
        int cur = q.top().second;
        q.pop();
        visited[cur] = true;

        for (int i = 0; i < graph[cur].size(); i++) {
            int  new_s = graph[cur][i].first;
            int new_c = graph[cur][i].second;
            //cost 업데이트
            if (cost[cur] + new_c < cost[new_s]) {
                cost[new_s] = cost[cur] + new_c;
                if (!visited[new_s]) q.push({ cost[new_s] , new_s });
            }
        }
    }
}

int main() {
    cin.tie(NULL);
    ios_base::sync_with_stdio(false);
    cin >> n >> m;
    int start_node;
    cin >> start_node;
    fill(cost, cost + n + 1, 987654321); //inf로 채워줌
    graph.resize(n + 1);
    for (int i = 0; i < m; i++) {
        int a, b, c;
        cin >> a >> b >> c;
        graph[a].push_back({ b, c });
        //  graph[b].push_back({a,c });
    }
    //시작점 
    cost[start_node] = 0;
    dijkstra(start_node);
    for (int i = 1; i <= n; i++) {
        if (cost[i] == 987654321) cout << "INF" << "\n";
        else cout << cost[i] << "\n";
    }
}