[알고리즘] 다익스트라(Dijkstra) 알고리즘

1. 다익스트라(Dijkstra) 알고리즘이란?

- 다이나믹 프로그래밍을 활용한 대표적인 최단 경로 탐색 알고리즘

- 특정한 하나의 정점에서 다른 모든 정점으로 가는 최단 경로를 알려줌. > 모든 정점을 방문하되, 최단 경로로!

- "최단 거리는 여러 개의 최단 거리로 이루어져있다."는 다이나믹 프로그래밍의 특성 반영

  > 하나의 최단 거리를 구할 때, 그 이전까지 구했던 최단 거리를 그대로 사용

- 가중치가 양수일 때만 사용 가능하다

---

2. 알고리즘의 동작 단계

(1) 출발 노드, 도착 노드 설정

(2) 출발 노드를 기준으로 각 노드의 최소 비용 저장

(3) 방문하지 않은 노드 중에서 가장 비용이 적은 노드 선택

(4) 해당 노드를 거쳐서 특정한 노드로 가는 경우를 고려하여 최소 비용을 갱신 > 간선 비용(가중치) 계산

(5) 3~4번을 반복

 

- 실제로 컴퓨터 안에서 탐색을 진행할 때는 이차원 배열 형태로 처리

회색 > 민트 이동	> 노드 1	>  노드 2	>  노드 3	>  노드 4	>  노드 5	>  노드 6
노드 1	0	2	4	1
노드 2	2	0	3	2
노드 3	5	3	0	3	1	5
노드 4	1	2	3	0	1
노드 5			1	1	0	2
노드 6			5		2	0

- 노드 1에서부터 시작! 

- 방문하지 않은 노드중에서 가장 비용이 적은 노드 선택

step 1. 경로: 1- 4 

0

2

5

1

무한

무한

step 2. (3번, 5번 노드에 가는 최소 경로를 갱신) 경로: 1 - 4 - 2 

0

2

4

1

2

무한

step 3. 경로: 1 - 4 - 2 - 5

0

2

4

1

2

무한

step 4. ( 3번, 6번 노드에 가는 최소 경로를 갱신)  경로: 1 - 4 - 2 - 5 - 3

0

2

3

1

2

4

step 5. ( 3번, 6번 노드에 가는 최소 경로를 갱신)  경로: 1 - 4 - 2 - 5 - 3 - 6

0

2

3

1

2

4

최종 경로: 1 - 4 - 2 - 5 - 3 - 6

---

3. 알고리즘의 시간 복잡도

- 선형 탐색(순차 탐색): O(N^2)

- 힙 구조(우선순위 큐): O(N * log N)

- 인접 리스트: O(N * log N)

---

4. BFS와 다익스트라 알고리즘의 비교

(1) BFS : 가중치 그래프에서 사용 X

- 가중치 없이 모두 동일한 상황 > 오래된 정점을 선택

- 적절한 자료구조 : 큐

 

(2) 다익스트라: 가중치 그래프에서 사용 O

- 가중치 존재 > 가중치에 따라 중요도의 순서가 바뀔 가능성 (순서는 상관 X)

- 각 상황에 맞는 최단 거리를 선택

- 적절한 자료구조: 우선순위 큐

---

5. 참고

- https://m.blog.naver.com/ndb796/221234424646

- https://velog.io/@717lumos/%EC%95%8C%EA%B3%A0%EB%A6%AC%EC%A6%98-%EB%8B%A4%EC%9D%B5%EC%8A%A4%ED%8A%B8%EB%9D%BCDijkstra-%EC%95%8C%EA%B3%A0%EB%A6%AC%EC%A6%98

- https://ansohxxn.github.io/algorithm%20lesson%202/chapter4-5/