자바 다익스트라(Dijkstra) 알고리즘 정의 및 작동 원리

다익스트라 알고리즘 (Dijkstra) 정의

음의 가중치가 없는 그래프의 한 노드에서 각 모든 노드까지의 최단거리를 구하는 알고리즘으로 BFS와 DP를 활용하는게 특징임

 

다익스트라 알고리즘 작동 원리

1. 방문하지 않은 정점들 중 거리가 짧은 정점부터 방문한다.

2. 해당 정점에서 인접하고 아직 방문하지 않은 정점들의 거리를 갱신한다.

 

예시를 보면서 살펴보겠다. 

A에서 E로 가는데 최단 거리는?

 

A → D → C → E : 1 + 2 + 6 = 9

A → C → E : 4 + 6 = 10

A  → B → D → C → E : 5 + 2 + 2 + 6 = 15

 

1. 시작 노드를 'A' 로 설정하고 이웃한 노드 중 거리가 짧은 순으로 노드를 선택해서 가중치(1, 4, 5)를 각 각 노드에 입력한다.

2. 1번에서 탐색한 노드 'D' 의 이웃한 노드 중 거리가 짧은 순으로 노드를 탐색하며 가중치 + 간선 가중치를 입력한다.

3. 재탐색하는 노드에는 기록된 가중치 + 간선 가중치와 비교해서 낮은 값을 입력한다.

 

위의 과정을 반복하면서 모든 노드를 탐색한다.

탐색하는 과정에서 BFS, 가중치를 기록하고 재사용하면서 DP를 사용하게 된다.

 

이제 최단 거리를 구해보겠다.

1. 시작지점과 연결된 노드들과 비용을 구한다.

<Result List>

연결된 노드	A	B	C	D	E
비용	0	5	4	1	INF

출발 지점이 A이기 때문에 자기 자신에게 가는 비용은 0이다.

A와 E로 바로 갈 수 있는 경로가 없기 때문에 INF (MAX_VALUE), 즉 가장 큰 값을 넣어준다.

 

2. 가장 작은 비용을 우선순위에 넣는다.

<Priority Queue>

우선 순위 큐	D	C	B
비용	1	4	5

우선 순위 큐는 비용이 가장 낮은 것을 우선으로 추출한다.

하나씩 추출하면서 연결된 다른 노드들의 비용을 확인하고 갱신한다.

D와 연결된 노드	A	B	C	D	E
비용	-	-	2	-	-

D와 연결된 노드는 C 노드 뿐이다.

우선 순위 큐에서 꺼낸 D는 이미 1의 비용을 가지고 있기 때문에 C로 가기 위해서는 1+2 비용을 가진다.

결론은 A에서 C까지 가는데 3의 비용을 가지고 현재 Result List에 들어있는 비용(4)와 비교해서 더 적은 값인 3으로 갱신해준다.

 

<Priority Queue>

우선 순위 큐	C	C	B
비용	3	4	5

C와 연결된 노드는 E이고 비용은 6이다. 

현재 A → E까지의 비용은 INF보다 적기 때문에 3+6 = 9를 우선 순위 큐에 넣어준다.

 

<Result List>

연결된 노드	A	B	C	D	E
비용	0	5	3	1	9

<Priority Queue>

우선 순위 큐	C	B	E
비용	4	5	9

목표 노드인 E까지 도착했으니까 이젠 우선 순위 큐에서 C를 선택하고 연결된 E와의 비용을 합치면 A → E = 10이다.

하지만 현재 Result List에 E까지의 비용이 더 적기 때문에 갱신하지 않고 끝낸다.

 

다음 순서는 B이다. B와 연결된 D와의 비용 합이 Result List에 D값보다 크기 때문에 갱신하지 않는다. 이와 같은 방법으로 우선 순위 큐를 끝까지 돌리면 아래와 같은 결과가 나온다.

 

<Result List>

연결된 노드	A	B	C	D	E
비용	0	5	3	1	9