다익스트라(dijkstra)

정의

다익스트라 알고리즘은 그래프에서 최단거리를 구하는 알고리즘.

 

특징

출발 노드와 모든 노드 간 최단거리를 탐색합니다: 다익스트라 알고리즘은 그래프의 한 노드(출발 노드)에서 시작하여 다른 모든 노드로 가는 최단거리를 계산합니다. 이는 주로 네트워크 경로 탐색, 지도 어플리케이션 등에서 활용됩니다.

 

엣지는 모두 양수여야 합니다: 다익스트라 알고리즘은 엣지의 가중치가 모두 양수일 때만 올바르게 동작합니다. 음수 가중치가 있을 경우 다른 알고리즘, 예를 들어 벨만-포드 알고리즘을 사용해야 합니다.

 

알고리즘 동작 과정

다익스트라 알고리즘의 기본적인 동작 과정은 다음과 같습니다:

1. 초기화: 출발 노드를 설정하고, 출발 노드에서 자신으로의 거리를 0, 다른 모든 노드로의 거리를 무한대로 설정합니다.
2. 우선순위 큐 사용: 우선순위 큐(또는 최소 힙)를 사용하여 현재 가장 가까운 노드를 선택합니다.
3. 최단거리 업데이트: 선택된 노드와 연결된 모든 인접 노드에 대해 현재 알려진 최단거리보다 더 짧은 경로가 발견되면 최단거리를 업데이트합니다.
4. 반복: 모든 노드가 처리될 때까지 2번과 3번 과정을 반복합니다.

 

시간복잡도 (E: 엣지, V: 노드)

 O(ElogV) (E: 엣지의 수, V: 노드의 수)

 

이는 우선순위 큐를 사용하여 가장 효율적인 방식으로 구현했을 때의 시간 복잡도입니다.

우선순위 큐를 통해 노드를 선택하고, 각 엣지를 확인하면서 최단거리를 업데이트하는 과정에서 이 복잡도가 도출됩니다.

 

 

예제로 전체적인 흐름 보기

간단한 예제를 통해 다익스트라 알고리즘의 동작을 살펴보겠습니다:

인접 그래프가 다음과 같다고 가정해보겠습니다.

 

 

1. 인접 리스트 구현

인접 행렬로 구현도 가능하겠지만, 노드의 수가 커질 것을 대비하여 인접리스트로 구현합니다.

예로 1000000*1000000행렬로 만들게 되면 0~9999999까지 선행 탐색을 해야하기 때문에 시간복잡도가 늘어납니다.

이를 대비해 인접리스트로 구현합니다.

1 -> [2,8][3,3]

2-> [4,4][5,12]

3-> [4,11]

4 -> [5,2]

5 -> X

2. 최단거리 배열 초기화

최단 거리 배열을 만들고, 출발노드는 0, 이외 노드는 MAX로 초기화합니다.

1이 시작점이라고 가정하였으니

S[N]

1	2	3	4	5
0	MAX	MAX	MAX	MAX

 

3. 최저값 노드 고르기

최단거리 배열 S[N]에서 가장 작은 노드를 선택합니다.

가장 처음엔 시작노드가 되겠죠?

1	2	3	4	5
0	MAX	MAX	MAX	MAX

-> 이때 Edge가 Generic인 우선순위큐를 사용하여 최소거리인 노드를 Poll한다.

 

4. 최단 거리 배열 업데이트

선택된 노드에 연결된 엣지를 순회하며 다른 노드에 값을 업데이트 해줍니다.

1 -> [2,8][3,3]

1 -> [2,8][3,3]

 * 최단거리 노드 업데이트 로직

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

   1 -> 2를 예로 들면 MIN(0+8 , MAX)

 

5. 과정 3~4를 반복하여 최단거리 배열 완성

 

초기값, 1 ~5 번 노드를 순차적으로 선택하면서 최단거리 배열 완성

* 편의상 1~5번 노드를 순차적으로 작성한 것이며,
   실제로는 PQ에 가중치를 기준으로 정렬되기 때문에 1-3-2 순으로 진행된다.

1	2	3	4	5
0	MAX	MAX	MAX	MAX
0	8	3	MAX	MAX
0	8	3	12	20
0	8	3	12 (12<14)	20
0	8	3	12	14
0	8	3	12	14

 

완성된 배열 (시작노드 1에서 i노드까지 가는데 걸리는 최단 시간을 의미)

 

1	2	3	4	5
0	8	3	12	14

 

활용 문제

https://true-false.tistory.com/37