c++/알고리즘

[c++] 다익스트라 알고리즘 (백준-최단경로 1753)

hojung 2023. 1. 25.

728x90

다익스트라 알고리즘이란?

다익스트라 알고리즘이란 한 지점에서 그래프 상의 나머지 모든 지점으로의 최단 경로를 구할 수 있는 알고리즘이다.

다익스트라 알고리즘은 그래프 상의 어느 한 간선의 가중치라도 음수가 존재하면 안된다. 이는 다익스트라 알고리즘이 현재 선택하는 것이 최선의 방법이라는 greedy를 기반으로 한 알고리즘이기 때문이다.

만약 음수의 가중치가 있다면 이 경로를 계속 지나갈수록 더욱 최선의 값을 가지게 되므로 다익스트라 알고리즘에 위배된다. (음수의 가중치를 가질 수 있을 때는 벨만 포드 알고리즘을 이용해야한다.)

다익스트라 알고리즘을 구현하기 위해서는 2가지의 과정을 반복해주면 된다.

/*
	1. 방문하지 않은 정점 중 가장 가중치 값이 작은 정점을 방문한다. -> 이를 위해 처음 배열을 무한대 값으로 초기화해준다. 
    2. 해당 정점을 거쳐서 갈 수 있는 정점의 거리가 이전에 기록한 거리보다 짧다면 업데이트 해준다.
*/

다익스트라 알고리즘은 다음과 같은 과정을 거친다.

우선 시작 정점으로 부터 연결된 모든 정점의 거리를 업데이트한다.

그 후 가장 가중치가 작은 노드로 이동해 그 노드로부터 연결된 모든 노드들의 거리를 업데이트한다.

업데이트가 된다는 것은 기존 경로로 이동하는 것보다 새로운 노드를 거쳐서 도착 노드로 이동하는 것이 더 적은 가중치를 갖는 것을 의미한다.

생각해봐야 할 것

다익스트라 알고리즘은 시작노드로부터 연결된 모든 노드를 탐색한다음 가장 작은 가중치를 갖는 노드로 이동하기 때문에 정렬 과정이 필요하다. 하지만 정렬은 대부분 O(N)이상의 시간복잡도를 갖는 경우가 많다. 하지만 자료구조 heap을 이용한다면 O(logN)의 시간복잡도만에 정렬을 수행하고 필요한 노드를 꺼내올 수 있다. 따라서 다익스트라 알고리즘을 구현할 때에는 c++의 STL에 존재하는 Priority Queue를 이용하는 경우가 많다. Priority Queue를 이용하면 자동으로 heap 정렬을 수행해주기 때문이다.

그러면 priority queue에 어떤 데이터를 집어넣고 무슨 기준으로 정렬을 수행해야할까?

아 알고리즘 설명에 따르면 출발 노드로부터 가장 가중치가 작은 노드를 우선적으로 꺼내온다고 했다.

또한 하나의 노드는 여러 개의 노드와 연결될 수 있고 최대 몇 개의 노드와 연결될 수 있는 지는 잘 알 수 없다. 물론 총 노드의 수보다는 적겠지만 쓸모없는 배열을 모두 할당해두는 것은 메모리 적으로 큰 낭비이다.

따라서 동적으로 할당된 메모리를 변경할 수 있는 <vector> 가 유용할 거 같다.

또한 연결된 거리와 꺼내오는 노드는 각각 다른 데이터를 갖는다. 즉 heap 정렬에 필요한 데이터와 heap정렬의 결과를 통해 꺼내와야하는 데이터는 다르다는 뜻이다. 그래서 구조체를 선언하는 것이 효과적일 거 같았다.

백준 - 최단경로 1753

이 문제는 전형적인 다익스트라 알고리즘을 구현하는 문제로써 문제는 다음과 같다.

문제

입 출력

코드

#include <cstdio>
#include <priority_queue>
#include <vector>
#define MAX 200002
#define INF 0x3f3f3f3f
using namespace std;
int V, E , K; // 정점과 간선의 개수
struct n_t {
	int cost; // 거리
    int node; // 노드번호
    inline bool operator < (const n_t &ref) const{
    	return this->cost > ref.cost;
    }// 오름차순 정렬 작은게 앞
}

int dist[MAX]; // 거리를 업데이트 할 배열
vector<n_t> AL[MAX]; // 인접 행렬을 나타낼 벡터

void init() {
	scanf("%d %d %d", &V, &E, &K);
    
    for(int i=0; i< E; i++) {
    	int a, b, c;
    	scanf("%d %d %d" , &a, &b, &c);
        AL[a].push_back({b,c});
    }
    for(int i=1; i<=V; i++) {
    	dist[i] = INF; // 무한대로 초기화
    }
}

void dijkstra() {
	priority_queue<n_t> pq;
    dist[K] = 0; // 시작 정점 업데이트
   	pq.push({K,0}); // 시작 노드 넣어준다.
    
    while(pq.size()){
    	n_t curr = pq.top(); pq.pop();
        for(n_t next : AL[curr]) {
        	int cost = dist[curr.node] + next.cost; 
        	if(cost < dist[next.node]) {
            	dist[next.node] = cost; // 거리 업데이트
                pq.push({next.node, cost}); // pq에 넣어주기 
            }
        } // curr의 인접 행렬을 모두 탐색 
    }
}