[알고리즘] 최단 경로 알고리즘 : 다익스트라 (Dijsktra)

다익스트라(Dijsktra)

• 단일 시작점 최단거리 알고리즘
• 너비 우선 탐색(BFS)과 유사한 형태를 가진 알고리즘
• 큐 대신 우선순위 큐(PriorityQueue)를 사용해 최단 거리를 기준으로 정점을 배열해 문제를 해결
• 음수 간선을 포함할 수 없음

동작 과정

1. 출발 노드 방문 및 출발 노트 최소 비용 0으로 초기화
2. 출발 노드 기준 각 노드별 최소 비용 저장
3. 방문하지 않은 노드 중 가장 최소 비용 노드 선택
4. 해당 노드를 거쳐 특정 노드로 가는 경우 고려해 최소 비용 갱신
5. 3,4 반복

1.

기본 그래프 확인

2.

출발 노드 방문 및 출발 노트 최소 비용 0으로 초기화한다.

출발 노드 0의 최소 비용을 0으로 초기화한다. 

3.

출발 노드 기준 각 노드별 최소 비용 저장한다.

출발 노드 0을 기준으로 연결된 노드 1과 노드 2를 최소 비용으로 업데이트하고

우선순위 큐에 노드 인덱스와 간선 가중치의 값인(2, 1)과 (1, 5)를 추가한다.

4.

오름차순으로 정렬된 간선 가중치를 담은 우선순위 큐에서 (3,1)이 poll 된다.

poll 하기 전 우선순위 큐에 담긴 값 : (2, 1), (1, 5)

이때, 노드 3과 연결된 노드 0과 노드 3 중 distance [cur.n] + next.w < distance [next.n] 식에 의해 

노드 3을 최소 비용으로 업데이트하고

우선순위 큐에 노드 인덱스와 간선 가중치의 값인(3, 3)를 추가한다.

5.

오름차순으로 정렬된 간선 가중치를 담은 우선순위 큐에서 (3, 3)이 poll 된다.

poll 하기 전 우선순위 큐에 담긴 값 : (3, 3), (1,5)

이때, 노드 3과 연결된 노드 1, 노드 2와 노드 6 중 distance [cur.n] + next.w < distance [next.n] 식에 의해 

노드 1, 노드 2와 노드 6을 모두 최소 비용으로 업데이트하고

우선순위 큐에 노드 인덱스와 간선 가중치의 값인 (1,4), (4,8), (6,6)를 추가한다.

6.

오름차순으로 정렬된 간선 가중치를 담은 우선순위 큐에서 (1,4)이 poll 된다.

poll 하기 전 우선순위 큐에 담긴 값 : (1,4), (1,5), (6,6), (4,8)

이때, 노드 1과 연결된 노드 3, 노드 5와 노드 6 중 distance [cur.n] + next.w < distance [next.n] 식에 의해 

노드 5를 최소 비용으로 업데이트하고

우선순위 큐에 노드 인덱스와 간선 가중치의 값인 (5,7)를 추가한다.

7. 

poll 하기 전 우선순위 큐에 담긴 값 : (1,5), (6,6), (5,7), (4,8)

distance [cur.n] + next.w < distance [next.n] 식에 의해 더 이상 최소 비용으로 업데이트되는 노드가 없어 계속 poll 한다.

static int n; // 정점의 개수
static int m; // 간선의 개수
static ArrayList<path>[] al = new ArrayList[n+1]; // 그래프의 (연결 정점 번호, 간선 가중치)쌍을 담는다.
static int distance[] = new int[n+1]; // 그래프의 거리를 담는 변수
		
Arrays.fill(distance, Integer.MAX_VALUE);

for(int i = 0; i < n+1; i++) {
	al[i] = new ArrayList<>();
}

// 간선 입력  (a, b, c): a -> b 로 가는 가중치 c을 가지는 간선
for(int i = 0; i < m; i++) {
	StringTokenizer st = new StringTokenizer(br.readLine());
	int a = Integer.parseInt(st.nextToken());
	int b = Integer.parseInt(st.nextToken());
	int c = Integer.parseInt(st.nextToken());
	al[a].add(new path(b, c));
}


static void Dijkstra() {
	PriorityQueue<path> pq = new PriorityQueue<>(); // 우선순위 큐
	pq.offer(new path(start, 0));
	distance[start] = 0;
		
	while(!pq.isEmpty()) {
		path cur = pq.poll();
			
		for(path next: al[cur.n]) {
			if(distance[cur.n] + next.w < distance[next.n]) {
				distance[next.n] = distance[cur.n] + next.w;
				pq.offer(new path(next.n, distance[next.n]));
			}
		}
	}
}

static class path implements Comparable<path>{
	int n; // 정점
	int w; // 가중치
		
	path(int n, int w) {
		this.n = n;
		this.w = w;
	}

	@Override
	public int compareTo(path o) { // 가중치를 오름차순으로 정렬
		return this.w - o.w;
	}
}