[C++알고리즘][다익스트라 알고리즘 개념설명]-최단거리 알고리즘

다익스트라 알고리즘은 출발 노드로부터 각 노드들의 최단거리를 구하는 알고리즘이다.

다익스트라 알고리즘을 이해하기 위해서는 일단 인접 리스트에 대해서 먼저 공부해야 이해할 수 있으므로 인접 리스트에 대해서 공부해오자.

 예를 들어서 설명해보겠다.

 

 

위와 같은 가중치가 있는 그래프가 있다.

여기서 출발지가 1이라고 했을 때 각 노드들로 가는 최단경로를 구하는 것이 다익스트라 알고리즘이다.

 

1	2	3	4	5
infy	infy	infy	infy	infy

위와 같이 최단거리를 저장해두는 배열 dist를 생성한다.

초기값은 무한으로 해둔다.

 

다익스트라 알고리즘은 다음 노드의 dist 값과 현재노드의 dist값+가중치를 비교하여 더 작은 값이 다음 노드의 dist가 되는 알고리즘이다.

1을 출발선이라고 하고 위의 설명과 같이 dist배열의 변화를 보겠다.

 

 

1	2	3	4	5
0	infy	infy	infy	infy

1이 출발선이기 때문에 1->1의 최단거리는 당연히 0이다.(자기 자신이 도착지) 그러기에 처음에 출발지의 dist값은 0으로 초기화하고 시작해야 한다.

 

이제 노드 1과 연결된 노드 2와 노드 3을 방문하게 된다.

노드 2부터 방문해보겠다.

노드 1 -> 노드 2의 가중치의 값은 2이다. 현재 노드 dist값+가중치를 하면 2가 나오는 걸 알 수 있다.(dist [1] = 0이기 때문에)

그리고 dist [2]의 값은 infy(무한) 이므로 둘을 비교하면 2가 작으므로 dist [2]의 값은 2로 바뀌게 된다.

 

 

1	2	3	4	5
0	2	infy	infy	infy

노드 1-> 노드 3을 방문할 때도 dist [3]의 값은 무한이기에 가중치+dist [1]인 3이 된다.

 

1	2	3	4	5
0	2	3	infy	infy

이제 노드 2-> 노드 3을 방문할 차례이다.

현재 노드 dist값+가중치의 값은 dist [2]+4 이므로 6이다.

dist [다음 노드]의 값은 dist [3]이기 때문에 3이다.

둘 중 더 작은 값이 dist[3]이 되므로 3이 dist [3]의 값이 된다.

 

1	2	3	4	5
0	2	3	infy	infy

그러므로 전과 변화가 없다.

 

이제 어느 정도 이해가 된 것으로 알고 배열의 변화만 알아보도록 하겠다.

노드 2-> 노드 5

1	2	3	4	5
0	2	3	infy	5

 

 

노드 2-> 노드 4

1	2	3	4	5
0	2	3	7	5

 

 

노드 3-> 노드 4

1	2	3	4	5
0	2	3	7	5

 

 

노드 1-> 노드 5

1	2	3	4	5
0	2	3	7	4

 

 

최종 dist배열

1	2	3	4	5
0	2	3	7	4

 

다익스트라 알고리즘에서 중요한 것은 최소 힙을 이용한다는 것이다. 다음 노드와 현재 노드의 최단거리를 최소 힙으로 큐에 저장하고 꺼내 쓰는 구조로 탐색하게 된다. 자세한 건 코드를 보면서 이해하는 게 빠를 것이다.

 

코드

#include <iostream>
#include <queue>
#include <vector>
#define max 100
#define infy 987654321
using namespace std;
vector <pair<int,int>> adj[max]; // 노드들의 정보들을 담는 벡터
int dist[max]; //최단거리를 저장하는 배열
int V,E;
// dist배열을 초기화 하기 위한 함수
void dist_set(void){
    for(int i = 1;i<=V;i++){dist[i] = infy;}
}
void dijkstra(int node){
    priority_queue<pair<int,int>> pq; // 우선순위 큐 생성
    pq.push(make_pair(0,node)); // 최소힙 생성
    while(!pq.empty()){ // 만약 pq의 아무것도 없다면 그만
        node = pq.top().second; // 노드를 불러온다
        pq.pop(); // 불러온 노드 큐에서 삭제
        for(int i = 0;i<adj[node].size();i++){
            int next_node = adj[node][i].first; //다음노드
            int new_val = adj[node][i].second + dist[node]; //다음 노드로 가는 새로운 최단거리
            int before_val = dist[next_node]; //다음노드의 원래 최단거리
            if(new_val < before_val){ // 만약 새로운 최단거리가 더 작으면 교체
                dist[next_node] = new_val;
                pq.push(make_pair(-1*new_val,next_node)); // -1를 하는 이유: 최소힙을 만들기 위해(top을 했을때 가장 작은 값이 나오게 하기 위함)
            }
        }
    }
}
int main(void){
    cin >> V >> E; //V는 정점의 갯수, E는 간선의 갯수
    for(int i = 0;i<E;i++){
        int u,v,w;
        cin >> u >> v >> w;
        adj[u].push_back(make_pair(v,w)); //adj[노드].<노드,가중치>구조 
    }
    dist_set(); //dist배열 초기화 해준다.
    dist[1] = 0; //시작점 초기화
    dijkstra(1);
    for(int i =1 ;i<=V;i++){cout << dist[i] << " ";}
}

 

 

추천 문제

https://www.acmicpc.net/problem/1753

1753번: 최단경로

https://www.acmicpc.net/problem/1916

1916번: 최소비용 구하기

https://www.acmicpc.net/problem/1504

1504번: 특정한 최단 경로

https://www.acmicpc.net/problem/1854

1854번: K번째 최단경로 찾기

https://www.acmicpc.net/problem/14938

14938번: 서강그라운드

https://www.acmicpc.net/problem/11779

11779번: 최소비용 구하기 2