다익스트라 Djikstra 최단경로 알고리즘 (C++코드, Java코드)

다익스트라 알고리즘은 가장 기본적인 최단경로 알고리즘이다.

가장 기본적이란 말은 이외에도 벨만 포드, 플로이드 와샬 알고리즘이 있는데,

상대적으로 다익스트라가 대회에 많이 출제되기도 하고, 셋 중에 시간복잡도가 가장 빠른 알고리즘이기 때문에 꼭 숙지하는 것이 좋다.

(참고로 시간복잡도는 각각 다익스트라 O(ElogV) / 벨만포드 O(VE) / 플로이드 와샬 O(V^3), 각각 사용되는 상황이 다름)

 

 

다익스트라 알고리즘은 한 정점에서 다른 모든 정점까지의 최소비용(최단거리)을 구하는 알고리즘이다.

내가 다익스트라를 사용하는 문제 유형은 다음과 같다.

1. 최단거리 / 최소비용 문제이다.

2. 문제를 읽었을 때, 문제의 의도가 한두 개의 적은 수의 출발점을 강조한다. (만약 모든 출발점이라면 플로이드와샬)

3. 음의 간선이 존재하지 않는다. (만약, 음의 간선이 존재할 경우 벨만포드)

 

코드를 바로 살펴보자.

#include <iostream>
#include <vector>
#include <queue>
using namespace std;

//최소비용은 INF를 넘을 수 없다.
const int INF = 987654321;
//정점 최대 개수
const int MAX_V = 20001;

int v, e, k; //v 정점 수, e 간선 수, k 시작지점
vector<pair<int, int>> adj[MAX_V]; //인접 리스트 표현 pair(w, r) w: 가중치 r: 도착점
priority_queue<pair<int, int>> pq; //다익스트라에 사용할 우선순위큐 pair(w,r) w: 가중치 r: 도착점

vector<int> Djikstra(int st) {

	// 최단거리 값을 담을 INF로 초기화한 벡터 선언 ret[도착점] = 최단거리
	vector<int> ret(v, INF);
    // 시작점 0으로 초기화, 우선순위 큐에 넣기
	ret[st] = 0;
	pq.push(make_pair(0, st));
    
    //모든 정점을 돌 때까지 반복
	while (!pq.empty()) {
    	// pq에 담긴 값 중 가장 weight가 작은 것 꺼내기
		int now = pq.top().second;
        // 마이너스를 붙여서 꺼낸 이유는 기본 우선순위 큐가 maxheap이라서 가장 작은 값을 꺼내기 위해 마이너스 붙임.
        // 37번행에서 마이너스를 붙여서 넣으므로 꺼낼 땐 기존 값으로 나옴.
		int weight = -pq.top().first; 
		pq.pop();

		//사실상 시간이 단축되는 코드. 꺼낸 것 보다 현재  가중치가 작으면 돌필요 없어서 버림.
		if (weight > ret[now]) continue;

		for (int i = 0; i < adj[now].size(); i++) {
			int there = adj[now][i].second;
			int cost = adj[now][i].first+weight;
            // 만약 더 작은 가중치를 찾으면 ret 값을 바꿔주고 그 정점에서 한 번 더 탐색하기 위해 pq에 추가.
			if (cost < ret[there]) {
				ret[there] = cost;
				pq.push(make_pair(-cost, there));
			}
		}
	}
	return ret;
}

int main() {
	cin.tie(0);
	ios_base::sync_with_stdio(false);
    
    //입력
	cin >> v >> e>>k;
	for (int i = 0; i < e; i++) {
		int a, b, c;
		cin >> a >> b >> c;
		adj[a].push_back(make_pair(c, b));
	}
    
    //함수호출
	vector<int> ans = Djikstra(k);
    
    //출력
	for (int i = 0; i < ans.size();i++) {
		if (ans[i] == INF)cout << "INF\n";
		else cout << ans[i] << '\n';
	}
}

 

public class Solution{
    static int V, E;
    static List<Edge>[] edges;

    private static int[] djikstra(int start) {
        int[] distance = new int[V + 1];

        Arrays.fill(distance, INF);
        distance[start] = 0;

        boolean[] visited = new boolean[V+1]; //각 노드당 한 번만 방문

        PriorityQueue<Edge> pq = new PriorityQueue<>();
        pq.add(new Edge(0, start));

        while (!pq.isEmpty()) {
            Edge minEdge = pq.poll();
            int now = minEdge.node;
            int nowWeight = minEdge.weight;
            if (nowWeight > distance[now])
            	continue;
            visited[now] = true;
            for (Edge edge : edges[now]) {
                int next = edge.node;
                int nowToNext = distance[now] + edge.weight;
                if (!visited[next] && nowToNext < distance[next]) {
                    distance[next] = nowToNext;
                    pq.add(new Edge(nowToNext, next));
                }
            }
        }
        return distance;
    }

    private static class Edge implements Comparable<Edge> {
        int weight, node;

        Edge(int w, int d) {
            weight = w;
            node = d;
        }

        @Override
        public int compareTo(Edge o) {
            return Integer.compare(weight, o.weight);
        }
    }
}

두 코드가 구현에 있어서 약간의 차이는 있지만, 과정은 일치한다.

 

코드의 핵심은 다음과 같다.

 

1. 인접리스트 방식으로 간선을 저장한다.

C++ 코드의 adj, Java 코드의 edges가 바로 그것이다.

 

2. 우선순위 큐를 사용한다.

지금 상황에서 갈 수 있는 정점 중, 가장 작은 비용으로 갈 수 있는 정점을 선택하기 위해 사용한다.

우선순위 큐는 배열의 최대값 또는 최소값을 O(1)로 꺼낼 수 있고, 값을 추가/제거할 경우 O(logn)을 보장하기 때문에,

업데이트가 자주 일어나지만 최대값 또는 최소값을 가장 빠르게 찾아야 하는 상황에서 최적으로 사용할 수 있는 자료구조이다.

 

3. 다익스트라 함수는 출발 정점을 입력으로 받아 정수 배열을 리턴한다.

정수 배열은 각각 인덱스를 도착 정점으로 하고, 해당 정점까지의 최소비용을 담아 리턴한다.