[그래프] 다익스트라

다익스트라

그래프에서 최단 거리를 구하는 알고리즘

기능	특징 (제약조건)	시간 복잡도 (노드 수: V,  엣지 수:E)
출발 노드와 모든 노드간의 최단 거리 탐색	엣지는 모두 양수	O(ElogV)

 

핵심이론

5단계로 구현한다

 

[그래프]

８　15 ① → ② → ⑤ ↓3   ↓4 ↗2 ③ → ④  　13

 

Step 01) 인접 리스트로 그래프 구현

① → [ ②, 8 ] [ ③, 3 ]

② → [ ④, 4 ] [ ⑤, 15 ]

③ → [ ④, 13 ]

④ → [ ⑤, 2 ]

⑤

그래프 데이터를 자료구조 ArrayList 에 저장한다

 

다익스트라 알고리즘은 인접 행렬로 구현해도 좋으나 시간복잡도 측면 N의 크기가 클 것을 대비해 인접리스트를 선택하여 구현하는 것이 좋다.

 

Step 02) 최단거리 배열 초기화

 

최단거리 배열 생성 후 출발노드 0, 이외의 노드는 무한∞으로 초기화한다.

(여기서 말하는 무한이란 적당히 큰 값을 뜻함)

최단거리 배열 D[N]		노드	1(출발)	2	3	4	5
		거리	0	∞	∞	∞	∞

 

Step 03) 거리 값이 가장 작은 노드 선택

최단거리 배열 D[N]		노드	1	2	3	4	5
		거리	0	∞	∞	∞	∞

최단거리 배열에서 거리 값이 가장 작은 노드는 값이 0인 노드 1이다 (처음 연산이므로 출발노드가 가장 작음)

 

Step 04) 최단거리 배열 업데이트 및 방문배열 체크

 

min(선택노드 최단거리배열 값 + 엣지가중치 , 연결노드의 최단거리 배열의값)

min함수의 두 매개변수 중 최소값을 구한다.

구해진 최소값으로 선택된 노드가 가리키는 노드의 값을 변경한다.

최단거리 배열 D[N]		노드	1	2	3	4	5
		거리	0	∞	∞	∞	∞

 

ex) 선택노드 1은 2와 3을 가리키므로 min연산을 2번 진행 

 

• 선택노드 1의 최단거리 배열 값 : 0
• 노드1과 노드 2의 간선 가중치 : 8
• 노드 2의 최단거리 배열 값 D[2] : ∞

D[2] = min(0+8, ∞) = 8

 

• 선택노드 1의 최단거리 배열 값 : 0
• 노드1과 노드 2의 간선 가중치 : 3
• 노드 2의 최단거리 배열 값 D[3] : ∞

D[3] = min(0+3, ∞) = 3

 

이후 해당 최소값을 최단거리 배열에서 1이 가리키는 각각의 노드에 해당하는 거리에 저장

최단거리 배열 D[N]		노드	1	2	3	4	5
		거리	0	∞↓ 8	∞ ↓ 3	∞	∞

 

* 과정 3에서 선택노드가 될 때 마다 다시 선택되지 않도록 방문배열을 생성하여 처리한다.

방문배열 visit[N]		노드	1	2	3	4	5
		방문여부	[ T ]	[ F ]	[ F ]	[ F ]	[ F ]

방문 배열 초기화를 통해 한번 선택된 노드에 대한 재선택을 방지한다.

 

Step 05) 과정 3~4를 반복하여 최단거리 배열 완성

모든 노드가 처리될 때 까지 과정 3~4를 반복한다.

 

Re 03) 거리값이 가장 작은 노드 선택

 

이전에 연산한 노드 1을 제외한 거리 값이 가장 작은 노드는 거리값이 3인 노드3이다.

최단거리 배열 D[N]		노드	1 [ T ]	2	3	4	5
		거리	0	8	3	∞	∞

 

Re 04) 최단거리 배열 업데이트 및 방문배열 체크 

 

• 선택노드 3의 최단거리 배열 값 : 3
• 노드3과 노드 4의 간선 가중치 : 13
• 노드 4의 최단거리 배열 값 D[5] : ∞

D[4] = min(3+13, ∞) = 16

 

이후 해당 최소값을 최단거리 배열에서 3이 가리키는 각각의 노드에 해당하는 거리에 저장

최단거리 배열 D[N]		노드	1	2	3	4	5
		거리	0	8	3	∞↓ 16	∞

 

방문 배열 초기화를 통해 한번 선택된 노드에 대한 재선택을 방지.

방문배열 visit[N]		노드	1	2	3	4	5
		방문여부	[ T ]	[ F ]	[ T ]	[ F ]	[ F ]

 

---

 

Re 03) 거리값이 가장 작은 노드 선택

이전에 연산한 노드 1, 3을 제외한 거리 값이 가장 작은 노드는 거리값이 8인 노드2 이다.

최단거리 배열 D[N]		노드	1 [ T ]	2	3 [ T ]	4	5
		거리	0	8	3	16	∞

 

Re04) 최단거리 배열 업데이트 및 방문배열 체크

선택노드 2는 4와 5를 가리키므로 min연산을 2번 진행 

• 선택노드 2의 최단거리 배열 값 : 8
• 노드2과 노드 4의 간선 가중치 : 4
• 노드 4의 최단거리 배열 값 D[4] : 16

D[4] = min(8 + 4 ∞) = 12

 

• 선택노드 2의 최단거리 배열 값 : 8
• 노드2과 노드 5의 간선 가중치 : 15
• 노드 5의 최단거리 배열 값 D[5] : ∞

D[4] = min(8+15, ∞) = 23

 

 

이후 해당 최소값을 최단거리 배열에서 3이 가리키는 각각의 노드에 해당하는 거리에 저장

최단거리 배열 D[N]		노드	1	2	3	4	5
		거리	0	8	3	16↓ 12	∞ ↓ 23

 

방문 배열 초기화를 통해 한번 선택된 노드에 대한 재선택을 방지.

방문배열 visit[N]		노드	1	2	3	4	5
		방문여부	[ T ]	[ T ]	[ T ]	[ F ]	[ F ]

 

---

Re 03) 거리값이 가장 작은 노드 선택

 

이전에 연산한 노드 1, 3, 2를 제외한 거리 값이 가장 작은 노드는 거리값이 12인 노드4이다.

최단거리 배열 D[N]		노드	1 [ T ]	2 [ T ]	3 [ T ]	4	5
		거리	0	8	3	12	23

Re 04) 최단거리 배열 업데이트 및 방문배열 체크 

 

• 선택노드 4의 최단거리 배열 값 : 12
• 노드3과 노드 4의 간선 가중치 : 2
• 노드 4의 최단거리 배열 값 D[5] : 23

D[4] = min(12+2, ∞) = 14

 

이후 해당 최소값을 최단거리 배열에서 3이 가리키는 각각의 노드에 해당하는 거리에 저장

최단거리 배열 D[N]		노드	1	2	3	4	5
		거리	0	8	3	12	23↓ 14

 

방문 배열 초기화를 통해 한번 선택된 노드에 대한 재선택을 방지.

방문배열 visit[N]		노드	1	2	3	4	5
		방문여부	[ T ]	[ T ]	[ T ]	[ T ]	[ F ]

---

 

Re 03) 거리값이 가장 작은 노드 선택

 

이전에 연산한 노드 1, 3, 2, 4를 제외한 노드는 5인데 가리키는 노드가 없다.

(길이가 0인 ArrayList)

알고리즘을 종료한다.

---

최단거리 배열 통합 진행 과정 표

			1	2	3	4	5
초기값			0	∞	∞	∞	∞
노드 1 선택			0	8	3	∞	∞
노드 3 선택			0	8	3	16	∞
노드 2 선택			0	8	3	12	23
노드 4 선택			0	8	3	12	14
☆ 최종 완성된 배열 결과값 (노드 5 엣지 무)			0	8	3	12	14
★ 시작노드 1 기준 각각의 최단 거리			① → ①	① → ②	① → ③	① → ④	① → ⑤

 

 

다익스트라 알고리즘은 출발노드와 그 외 노드간 거리를 구하는 알고리즘이다.

엣지는 항상 양수인 제약조건을 가진다.

출발노드와 도착노드 간의 최단거리를 구하는 알고리즘이 아닌!

지정한 출발노드와 이외의 모든 노드간의 최단거리를 각각 구하는 알고리즘이다!ㄹ