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

다익스트라 알고리즘이란?

DP를 활용한 최단 경로 탐색 알고리즘입니다.

특정한 하나의 정점에서 다른 모든 정점으로 가는 최단 경로를 알려줍니다.

이때 음의 간선은 포함할 수 없습니다.

 

다익스트라 알고리즘이 DP 문제인 이유는 ' 최단거리는 여러 개의 최단 거리로 이루어져 있기 때문입니다.'

 

예제 1

예를 들어 다음 그림과 같이 1번 노드부터 다른 노드로 가는 최단 경로를 구한다고 가정해 보겠습니다.

 

우선 1번 노드와 인접한 2번, 3번, 4번 노드 간의 최단 거리를 구합니다.

경로 1 -> 2의 비용은 3

경로1 -> 3의 비용은 6

경로1 -> 4의 비용은 7

 

이후, 1번 노드와 인접하면서 가장 비용이 적은 2번 노드를 방문합니다.

경로1 ->3의 비용은 원래 6이었는데 2를 경유해서 가는 경우 4로 업데이트됩니다.

Math.min(6,3+1) = 4

다익스트라 알고리즘은 위와 같은 방식으로, 현재까지 알고 있던 최단 경로를 계속해서 갱신합니다.

 

구체적인 동작 과정

1. 출발 노드를 정하기

2. 출발 노드를 기준으로, 출발 노드와 각 노드 간의 최소 비용 저장

3. 현재 방문하지 않은 노드 중에서 비용이 가장 적은 노드를 방문

4. 해당 노드를 거쳐서 특정 노드로 가는 경우를 고려하여, 최소 비용 배열 업데이트

5. 3~4번 과정의 반복

 

만약 가장 비용이 적은 노드를 방문하지 않는다면 어떻게 될까요?

만약 1번 노드 탐색 후 2번 노드 탐색이 아닌 4번 노드를 탐색한다면 어떻게 될까요?

초기 비용은 다음과 같습니다

• 경로 1 -> 2의 비용은 3
• 경로1 -> 3의 비용은 6
• 경로1 -> 4의 비용은 7

4번 노드와 인접한 노드들을 탐색해 봅니다.

경로 (1 -> 4-> 3)는 8로 경로 (1 -> 3)의 비용인 6보다 크니 업데이트되지 않습니다. 

 

3번 노드와 인접한 노드들을 탐색해 봅니다.

경로 (1 -> 3 -> 2)는 7로 경로 (1 ->3)의 비용인 3보다 크니 업데이트되지 않습니다.

경로 (1 -> 3 -> 4)는 7으로 경로 (1 ->4)의 비용인 7보다 작지 않으므로 업데이트 되지 않습니다.

 

2번 노드의 인접한 노드들을 탐색해 봅니다.

경로 (1 -> 2 -> 3)은 4로 경로 ( 1 ->3)의 비용인 6보다 작으므로 업데이트됩니다.

 

이렇게 되면 노드별 최소 경로는 0 3 4 7으로 저장됩니다.

하지만 실제 최소 경로는 0 3 4 5입니다.

 

따라서 Greedy적인 요소를 섞어 가장 비용이 적은 노드를 우선적으로 방문해 주어야 합니다.

 

예제 2

아래 그림과 같이 1번 노드로부터 다른 모든 노드로 가는 최단 경로를 구한다고 가정해보겠습니다.

노드 간의 비용은 2차원 배열(인접 행렬) 또는 2차원 리스트(인접 리스트)로 표현할 수 있습니다.

이때 "무한"은 현재 노드 기준으로 직접적으로 연결되지 않았음을 의미합니다. ( 나중에 갱신됩니다)

3행 4열의 값이 3이라는 것은, 3번 노드에서 4번 노드로 가는 비용이 3이라는 의미입니다.

 

우선 1번 노드를 방문합니다

1번 노드로부터 2번 3번 4번 노드로 가는 최소 비용을 업데이트합니다.

현재 방문하지 않은 노드 중에서 가장 비용이 적은 4번 노드를 방문합니다.

4번 노드와 연결되어 있으며 아직 방문되지 않은 노드는 2번, 3번, 5번 노드입니다.

기존의 1번 노드로부터 4번 노드까지 최소 비용으로 이동한 뒤, 2번, 3번, 5번 노드의 현재 비용과 비교합니다.

더 저렴한 비용으로 최소 비용 배열을 업데이트합니다.

현재 방문하지 않은 노드 중에서 가장 비용이 적은 2번 노드를 방문합니다.

2번 노드와 연결되어 있는 노드 중 방문되지 않은 노드는 3번 노드이므로

Math.min( 현재 2에 담긴 최소 비용 , 현재 3에 담긴 최소 비용)을 진행합니다.

더 저렴한 비용으로 최소 비용 배열을 업데이트합니다.

이것을 반복하게 되면 최종 배열은 다음과 같이 형성됩니다.

 

활용으로 백준의 1753번 최단경로를 풀어보세요

https://junuuu.tistory.com/209?category=977532 

[백준] 1753 : 최단경로 - 자바(JAVA)

 

활용으로 백준의 1238번 파티를 풀어보세요

https://junuuu.tistory.com/210?category=977532 

[백준] 1238번 : 파티 - 자바(JAVA)

 

 

 

출처

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

23. 다익스트라(Dijkstra) 알고리즘

https://www.youtube.com/watch?v=611B-9zk2o4&list=PLRx0vPvlEmdDHxCvAQS1_6XV4deOwfVrz&index=25 

https://wooono.tistory.com/397

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