Algorithm 공부 #16 - 다익스트라 알고리즘

 

 

Algorithm 공부 #16 - 다익스트라 알고리즘

 

 

✏️ 다익스트라 알고리즘(Dijkstra Algorithm)

다익스트라 알고리즘은 그래프 상에서 한 정점에서 다른 정점들간의 최단 거리를 구할 수 있는 알고리즘이다.

즉 도착 정점 뿐만 아니라 모든 다른 정점가지 최단 경로로 방문하며 각 정점까지의 최단 경로를 모두 찾을 수 있다.

매번 최단 경로의 정점을 선택해 탐색을 반복한다고 생각하면 될 것 같다.

시간복잡도는 O(ElogV)이며 이때 특징으로는 에지값이 모두 양수여야 한다.

최단 거리 알고리즘은 이외에도 벨만-포드 알고리즘, 플로이드-워셜 알고리즘이 있는데 이 알고리즘들은

후에 포스팅을 할 예정이다.

 

 

✏️ 구현 방법

1. 출발 노드와 도착 노드를 설정
2. '최단 거리 테이블'을 초기화(출발 지점을 0으로, 나머지는 무수히 큰 값으로 초기화)
3. 최단 거리 배열에서 값이 가장 작은 노드를 고르기(출발 노드)
4. 선택된 노드에 연결된 에지의 값을 바탕으로 다음 노드의 값을 업데이트
5. 최단거리 업데이트 : min(선택 노드의 최단거리배열값+에지 가중치, 연결 노드의 최단 거리 배열의 값)
6. 모든 노드가 반복될 때까지 3~5과정을 반복

 

✏️ 동작 예시

          먼저 위와 같은 그래프가 있다고 가정을 하고 먼저 출발 노드와 도착 노드를 정한다

          출발 노드는 1, 도착 노드는 6이다

 

           최단 거리 배열은 보통 1차원 배열로 설정하고 위에서 설명했던 것처럼 출발 노드를 0으로 설정하고 

           나머지 노드를 무수히 큰 값으로 초기화를 한다. 설명하기 쉽게 최단 거리 배열을 mdist로 명명하겠음

        최단 거리 배열에서 가장 값이 작은 1번 노드부터 탐색을 시작한다. 1번 노드는 2번 노드와 4번 노드로

        연결되어 있음을 알 수 있고 각각의 가중치는 2와 1이다. 1->4(1)이고 mdist[4]=inf이므로 둘 중에 1이 더

        작기 때문에 mdist[4]=1로 업데이트 된다. 마찬가지로 mdist[2]도 2로 업데이트 됨을 알 수 있다.

        그리고 방문 여부를 확인하는 배열을 만들어서 방문 표시를 해주어야 함 visited배열이라고 하겠음.

        1번 노드는 인접 노드까지 모두 탐색을 완료했으므로 visited[1] = true로 체크

         1번 노드를 탐색 후 mdist에서 가장 값이 작은 노드는 4번 노드가 되었으므로 4번 노드에서 탐색 시작

         4번 노드는 1번, 2번, 5번 노드와 연결되어 있음. 먼저 1번 노드는 visited[1] = true이므로 탐색 하지 않음

         2번 노드는 4번 노드에서 가게 되면 1+2=3(출발 노드가 1임을 항상 생각하기, mdist의 각 인덱스값은

         출발 노드부터의 최단 거리이다.)이고 mdist[2]=2이므로 mdist[2] = 2로 유지, 같은 방식으로 mdist[5]를

         계산해주면 mdist[5] = 2로 갱신. 4번 노드도 인접 노드를 모두 탐색했으므로 visited[5]=true로 변경

          mdist값 중 2번과 5번이 가장 작지만 인덱스가 작은 값을 우선시해준다고 가정하고 2번 노드 탐색

          2번 노드의 인접 노드인 3번과 4번 노드를 탐색해주고 위에서 했던 과정들을 똑같이 반복하면

          mdist[3] = 5, mdist[4] = 1로 업데이트 / 인접 노드를 모두 탐색한 2번 노드는 visited[2] =true로 변경

     이번에 탐색을 시작할 노드는 5번 노드이다

     5번 노드의 인접 노드는 6번 노드이고 똑같이 값을 업데이트 해주면 mdist[6] = 4가 된다

     마찬가지로 5번 노드도 탐색을 끝냈으므로 visited[5] = true로 변경

      다음으로 선택할 노드는 mdist값이 더 작은 6번 노드이다.

      하지만 6번 노드는 더 이어지는 노드가 존재하지 않고 도착 노드이기 때문에 알고리즘을 종료한다

      최종적인 최단 경로는 1 -> 4 -> 5 -> 6이 되고, 최단 길이는 4가 됨을 알 수 있다.

 

✏️ 특징

다익스트라 알고리즘은 방문하지 않은 노드 중 최단 거리인 노드를 선택하는 과정을 반복한다

각 단계마다 탐색 노드로 한 번 선택된 노드는 최단 거리를 갱신하고, 그 뒤에는 더 이상 갱신되지 않는다

그리고 맨 위에서 한 번 언급했지만 음수의 가중치가 있는 경우에는 사용할 수 없다

음수 가중치가 나오면 다른 알고리즘을 사용할 수 있다

 

 

✏️ 구현하기

순차적으로 탐색하거나 우선순위 큐를 이용하여 탐색하는 방법이 있다.

필자는 우선순위 큐를 이용해서 탐색하는 것을 추천한다.

순차적으로 탐색하게 된다면 위에서 방문하지 않은 노드 중 가장 거리값이 작은 노드를 고르는 과정이 필요한데

이때 노드의 앞부터 n개만큼 차례대로 탐색을 해야 한다, 그리고 그 과정을 각 노드마다 반복한다면 시간복잡도는

O(n^2)이 된다. 우선순위 큐(힙정렬)를 사용하면 거리값이 가장 작은 노드를 고르는 과정을 logN으로 줄일 수 있다.

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

using namespace std;

# define INF 99999999

// 시작 위치와 정점의 개수, 인접 행렬을 받아
// 최소 거리 행렬을 반환함
vector<int> dijkstra(int start, int N, vector<pair<int, int>> graph[])
{
    vector<int> dist(N, INF);  // 거리를 저장할 리스트 초기화
    priority_queue<pair<int, int>> pq;  // 우선순위 큐 선언

    dist[start] = 0;  // 시작 노드 거리를 0으로 함
    pq.push({ 0, start });  // 우선순위 큐에 넣기

    while (!pq.empty())
    {
        int cur_dist = -pq.top().first; // 큐에서 꺼내 방문하고 있는 정점의 거리
        int cur_node = pq.top().second;  // 정점의 인덱스(번호)
        pq.pop();

        for (int i = 0; i < graph[cur_node].size(); i++)
        {
            int nxt_node = graph[cur_node][i].first;  // 인접 정점 번호
            int nxt_dist = cur_dist + graph[cur_node][i].second;  // 인접 정점까지 거리

            if (nxt_dist < dist[nxt_node])  // 지금 계산한 것이 기존 거리값보다 작다면
            {
                dist[nxt_node] = nxt_dist;  // 거리값 업데이트
                pq.push({ -nxt_dist, nxt_node });  // 우선순위 큐에 넣기
            }
        }
    }

    return dist;  // start 노드로부터 각 노드까지 최단거리를 담은 벡터 리턴
}

int main()
{
    const int N = 10;  // 노드의 개수가 10개라 가정.
    int E = 20;  // 간선의 개수가 20개라 가정.
    vector<pair<int, int>> graph[N];  // 그래프 형태 선언

    for (int i = 0; i < E; i++)
    {
        int from, to, cost;  // 간선의 시작점, 끝점, 가중치
        cin >> from >> to >> cost;
        graph[from].push_back({ to, cost });  // 무향 그래프라 가정하므로 시작점과 끝점 둘 다 벡터에 넣어야 함
        graph[to].push_back({ from, cost });
    }

    vector<int> dist = dijkstra(0, N, graph);
    
    cout << "끝점까지의 최단거리" << dist[N - 1] << endl;
    
    return 0;
}

 

다음은 백준 문제를 통한 예시이다.

✏️ 백준 1753번 최단 경로

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

1753번: 최단경로

 

#include<iostream>
#include<queue>
#include<vector>
#include<limits.h>
using namespace std;

typedef pair<int, int>edge; // 자료형 설정
vector<bool>visit; // 방문 여부 배열
vector<int>mdistance; // 최단 거리 배열
vector<vector<edge>>mlist; // 인접 리스트
priority_queue<edge, vector<edge>, greater<edge>>q; // 

int main() {

	ios::sync_with_stdio(false);
	cin.tie(NULL);
	cout.tie(NULL);

	int V, E, K;
	cin >> V >> E >> K; // 정점, 간선, 출발지 입력
	visit.resize(V + 1); // 각 배열들 크기 설정
	mdistance.resize(V + 1);
	mlist.resize(V + 1);
	
	fill(visit.begin(), visit.end(), false);
	fill(mdistance.begin(), mdistance.end(), INT_MAX);
	for (int i = 0; i < E; i++) {
		int u, v, w;
		cin >> u >> v >> w;
		mlist[u].push_back({ v,w }); // 인접 리스트 업데이트
	}

	mdistance[K] = 0; // 출발 지점 최단 거리 0으로 변경
	q.push({ 0,K }); // q에 거리와 노드 푸쉬

	while (!q.empty()) {
		edge cur = q.top();
		q.pop();
		int c_v = cur.second; // 탐색 시작할 노드
		if (visit[c_v]) // 이미 탐색했던 곳이라면 continue
			continue;
		visit[c_v] = true;

		for (int i = 0; i < mlist[c_v].size(); i++) {
			edge tmp = mlist[c_v][i];
			int next = tmp.first; // 다음에 탐색할 노드
			int value = tmp.second; // 다음 노드까지의 가중치
			if (mdistance[next] > value + mdistance[c_v]) // 다음 노드의 최단 거리 배열 값보다
				// 현재 노드의 최단 거리 배열값 + 다음 노드까지의 가중치의 합이 더 작다면
				mdistance[next] = value + mdistance[c_v];
				q.push({ mdistance[next],next });
		}
	}
	for (int i = 1; i <= V; i++) {
		if (mdistance[i] == INT_MAX)
			cout << "INF" << '\n';
		else
			cout << mdistance[i] << '\n';
	}
}

 

 

 

✏️ 백준 1916번 최소비용 구하기

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

1916번: 최소비용 구하기

 

#include<iostream>
#include<limits.h>
#include<vector>
#include<queue>
using namespace std;

typedef pair<int, int > edge;
vector<vector<edge>>mlist;
vector<int>mdistance;
vector<bool>visit;
int dijkstra(int start, int end);
int main() {

	ios::sync_with_stdio(false);
	cin.tie(NULL);
	cout.tie(NULL);

	int N, M;
	cin >> N >> M;
	mlist.resize(N + 1); // 배열 크기 설정
	mdistance.resize(N + 1); // 배열 크기 설정
	visit.resize(N + 1);
	fill(visit.begin(), visit.end(), false); // 방문 배열 초기화
	fill(mdistance.begin(), mdistance.end(), INT_MAX); // 최단 거리 배열 초기화
	
	for (int i = 0; i < M; i++) {
		int u, v, w;
		cin >> u >> v >> w;
		mlist[u].push_back({ v,w }); // 인접 리스트 업데이트
	}
	
	int start, end; // 시작 지점과 도착 지점
	cin >> start >> end;

	cout << dijkstra(start, end); // 결과 출력
}
int dijkstra(int start, int end) {
	priority_queue < edge, vector<edge>, greater<edge>>q; // 큐 생성
	mdistance[start] = 0;
	q.push({ 0,start });
	while (!q.empty()) {
		edge cur = q.top();
		int c_v = cur.second;
		q.pop();
		if (visit[c_v]) // 탐색했던 노드라면 건너뛰기
			continue;
		visit[c_v] = true; // 방문 표시
		for (int i = 0; i < mlist[c_v].size(); i++) {
			edge tmp = mlist[c_v][i];
			int next = tmp.first; // 방문할 곳
			int value = tmp.second; // 방문하는 곳으로의 가중치
			if (mdistance[next] > mdistance[c_v] + value) {
				mdistance[next] = mdistance[c_v] + value;
				q.push({ mdistance[next],next });
			}
		}
	}
	return mdistance[end];
}

 

 

✏️ 백준 1854번 k번째 최단경로 찾기

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

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

 

✏️ 문제 풀이

 k번째 최단 경로를 찾는 것이 핵심 => 최단 거리 배열을 우선순위 큐 배열로 만들어서 자동으로 정렬되게 하자

인접 배열 형태로 저장

 다익스트라를 돌리면서 두 가지 경우의 수로 나누기

   1. mdistance[i].size() < k일때 => 이때는 최단 경로의 값들을 비교해도 되지 않으므로 우선순위 큐 배열에 그냥 push

   2. mdistance[i].size() >=k이고 mdistance[i].top(이 배열에서 가장 큰 최단거리 값) > 새로 추가될려는 최단거리

      라면 가장 큰 최단거리 값을 mdistance[i]에서 pop해주고 새로운 최단거리를 추가해주기

 k번째 경로를 찾으려면 노드를 여러 번 찾을 수도 있으므로 방문 여부 체크는 하지 않기

#include<iostream>
#include<queue>
#include<vector>
#include<limits.h>
using namespace std;

typedef pair<int, int>edge;
int mlist[1001][1001];
priority_queue<int>mdistance[1001];
int main() {

	ios::sync_with_stdio(false);
	cin.tie(NULL);
	cout.tie(NULL);

	int N, M, K;
	cin >> N >> M >> K;

	for (int i = 0; i < M; i++) {
		int start, end, value;
		cin >> start >> end >> value;
		mlist[start][end] = value; // 인접 배열 업데이트
	}

	priority_queue<edge, vector<edge>, greater<edge>>pq; // 우선순위 큐 생성
	pq.push({ 0,1 }); // 거리와 노드 푸쉬
	mdistance[1].push(0); // 최단 거리 큐배열 시작부분 0으로 초기화

	while (!pq.empty()) {
		edge tmp = pq.top();
		pq.pop();
		int node = tmp.second;
		for (int i = 1; i <= N; i++) { // 반복문 돌리기

			if (mlist[node][i] != 0) { // 연결된 노드에 대해서 검색하기
				
				if (mdistance[i].size() < K) {// 우선순위 큐 배열의 크기가 k보다 작다면 그냥 push
					int value = mlist[node][i] + tmp.first;
					mdistance[i].push(value);
					pq.push({ value,i });
				}
				else if (mdistance[i].top() > mlist[node][i] + tmp.first) { // 우선순위 큐 배열의 크기가 k보다 크다면
					mdistance[i].top(); // 그 배열에서 가장 큰 거리의 합이 새로 추가 될려는 값보다 크다면 기존의 값은 삭제
					mdistance[i].push(mlist[node][i] + tmp.first); // 새로운 최단 거리 추가
					pq.push({ mlist[node][i] + tmp.first,i }); // 큐에도 추가
				}
			}
		}
	}
	for (int i = 1; i <= N; i++) {
		if (mdistance[i].size() == K) // 사이즈가 같으면 k번째 거리를
			cout << mdistance[i].top() << '\n';
		else // 아니라면 -1을
			cout << -1 << '\n';
	}
}