다익스트라 알고리즘 개념 java

1. 개념

(1) What? 다익스트라 알고리즘이 무엇인가요? 💡

다익스트라 알고리즘은 한 정점에서 다른 정점으로 가는 최단 거리 비용을 구하는 알고리즘이다.
다익스트라를 사용하면 시작 정점 S에서 직,간접적으로 연결된 모든 정점으로 가는 최단 거리 비용을 한 번에 구할 수 있다.

(2) Why? 왜 해당 알고리즘을 써야 하나요? 🤔💭

해당 알고리즘을 처음 접한다면 아마 지금까지 가중치가 없는 그래프에 대해서 정점 간의 최단 거리를 구하는 문제만 접해왔을 가능성이 높다. 가중치가 없는 그래프에서의 정점 간의 최단 거리는 BFS를 활용하면 쉽게 풀렸다. 왜냐하면 정점 사이를 잇는 간선의 개수가 곧 비용임으로 BFS를 돌렸을 때, 만나기까지 사용하는 간선의 개수만 세면 되었기 때문이다.
하지만 가중치가 있는 그래프에서 최단 거리를 풀려면 더 이상 간선의 개수 = 비용이 아니기 때문에 BFS로 문제를 풀 수 없고, 다익스트라 등 다른 알고리즘을 활용해야한다. 오늘은 양의 가중치만 있는 그래프에서 활용하기 제일 쉽고 직관적인 다익스트라를 써서 가중치가 있는 그래프에서 최단 거리 비용을 구하겠다.

(3) How? 어떻게 구현 하나요? 🔎

구현에 앞서 알고 있어야할 개념이 있다. 바로 최단 거리 배열 (dist) 이다.

• 최단 거리 배열 (dist): 출발 정점을 S라 할 때, 현재 시점에서 S에서 각 정점까지의 최단 거리 비용을 저장한 배열이다. 즉 index: 정점 번호, value: 현재 시점에서 S ➜ 해당 정점까지의 최단 거리 비용 이다.
  여기서 현재 시점이 중요한 이유는 다익스트라를 진행하면서 최단 거리 배열 내용을 계속 갱신해나갈 것이기 때문이다. 다익스트라를 통해 S ➜ A까지의 최단 거리가 갱신되면 최단 거리 배열도 갱신된다.

구현은 다음과 같이 이루어진다.

★ 구현 과정 ★
a. 시작 정점 S를 기준으로 최단 거리 배열(dist)를 만들고 초기화한다.
b. 방문하지 않은 정점 중 시작 정점 S로부터의 거리가 최소인 정점을 선택한다.
c. 현 선택한 정점에서의 간선을 활용해 최단 거리 배열 dist를 갱신한다.
d. 모든 정점을 방문할 때까지 혹은 목적지까지 방문할 때까지 b,c 과정을 반복한다.

밑은 각 과정에 대한 상세 설명이다. 해당 설명의 이해가 아직 벅찬 것 같이 느껴지면 스킵하고 바로 예시를 보고와도 된다.

a. 시작 정점 S를 기준으로 최단 거리 배열(dist)를 만들고 초기화 한다.
그렇다면 index=S인 부분만 값이 0 이고, 나머지는 값이 INF가 될 것이다. 왜냐하면 아직 계산을 진행하지 않았음으로, 자기 자신으로 가는 최단 비용이 0인 것을 제외하면 다른 정점까지의 최단 거리를 아직 모르기 때문이다. 만약 S=1이라면 다음과 같은 최단 거리 배열이 나온다.

b. 방문하지 않은 정점 중 시작 정점 S로부터의 거리가 최소인 정점을 선택한다.
맨 첫 시작일 경우 당연히 시작 정점이 선택된다. 그 후는 방문하지 않았으면서 시작 정점과의 거리가 최소인 정점을 선택해야한다. 이것을 구현하는데는 2가지 방법이 있다.

• 첫 번째로, 방문배열을 활용하는 방법이다. 클래식하게, 특정 정점을 사용했을 때마다, 방문 처리를 하면 된다.
• 두 번째로, 최단 거리 기준 오름차순으로 정렬된 우선순위 큐를 활용하는 방법이다.
  해당 방법은 최단 거리를 갱신할 때마다, 갱신된 정점의 <번호, 시작 정점에서부터의 거리>를 우선순위큐에 넣는다. 그러면 우리가 b번 단계를 할 때마다 그저 우선순위큐에서 값을 꺼내기만 하면 되므로, 첫 번째 방법보다 간편하고 속도적으로도 빠르다.(속도 비교는 뒤에 설명) 다만 몇 가지 조건으로 거르기 작업이 필요한데 왜냐하면 우선순위큐에서 꺼낸 값에 대해서 이미 더 짧은 거리로 갱신된 경우, 이미 방문해버린 정점의 경우를 거르지 않고 계산하면 이미 처리한 부분에 대해서 중복 계산이 이루어지기 때문이다. 알고리즘 효율을 위해서 꼭 필요하다.

왜 방문하지 않은 정점 중 최단 거리 정점만 고르는가?

• 방문한 정점은 더 이상 최단 거리 갱신이 이루어지지 않는다.
• 따라서 방문한 정점을 한 번 더 가는 것은 계산이 중복되고 무한 루프에 빠진다.

왜 방문한 정점의 갱신이 이루어지지 않는지는 예시에서 더 설명하겠다.

c. 현 선택한 정점에서의 간선을 활용해 최단 거리 배열 dist를 갱신한다.
귀성길에 삼촌과 아버지의 대화를 들어본 적이 있는가? 우리 집은 새로 생긴 도로에 대해서 빠삭한 삼촌이 더 빠른 루트를 매번 알려준다. 삼촌의 말 덕분에 출발지에서 할머니집까지 가는 최단 거리가 갱신 되었다.

이 처럼 현재 방문 정점이 A이고, A에서 인접한 정점이 B라고 할 때,
dist[B] = Math.min(dist[B], dist[A] + A ➜ B 간선 비용) 으로 결정된다. 원래 목적지까지 가던길이 빠르냐, 시작 정점 ➜ 현재 방문정점까지 최단거리로 찍고, 현재 정점에서 다시 목적지로 가는 게 빠르냐 저울질 한다는 소리다.

d. 모든 정점을 방문할 때까지 혹은 목적지까지 방문할 때까지 b,c 과정을 반복한다.

3. 예시

다음과 같은 그래프에서 다익스트라 알고리즘을 쓴다고 가정해보자. 시작 노드는 1이고, 우리가 값을 얻고 싶은 목표 노드는 6이다.

시작 노드에 대해서 거리 방문 처리 및 거리 배열의 값을 0으로 세팅한다. (예시에서는 노란색으로 색칠을 방문으로 간주한다.)

다음과 같이 1번의 인접 노드인 2,3이 값을 최신화 한다. 방문하지 않은 노드 중에 가장 거리 배열 값이 작은 (시작 노드에서 갈 수 있는 최단 경로인) 값은 무엇인가? 답은 노드 3이다.

그럼 이제 3의 입장에서 거리배열을 갱신해보자. 방문 노드 제외하고 3에서 갈 수 있는 노드들은 2와 4번 노드이다.
2번의 경우를 생각해보면, 1 ➜2 와 1➜3➜2 중 최단 거리가 더 짧은 비용을 택하게 될 것이다.

2번 노드는 원래의 3이란 값이 더 최소값이라서 현행유지 할 것이다. 다음으로 1,3을 제외한 노드 중 시작 노드에서 가장 최단으로 갈 수 있는 노드는 2번임으로 2번을 선택한다.

방문하지 않는 노드들에 대한 갱신을 해보면, 4번 노드는 이전의 경로보다 현재 2번 노드를 통한 경로가 최단 경로라 갱신되는 것을 볼 수 있다. (2에서 3번 노드를 갱신하려고 해도, 최단 경로가 안되므로 갱신할 필요가 없다. - 이미 방문한 노드들은 방문 후 절대 값이 갱신 되지 않는다! 그 이유는 다음 장에서 설명하겠다.)

이제 그림으로만 진행하겠다.

도착 정점 방문을 마치는 순간 다익스트라 알고리즘은 끝난다. 1➜6 최단 경로 비용은 8이다.

4. 특징

(1) 방문한 노드의 값은 그 뒤로 갱신하려 해도 절대 갱신되지 않는다.

현 노드가 A일 때, 인접 노드를 B,C라고 하자. 이때 A에서 갈 수 있는 최단 경로의 노드가 B라서 B를 방문했다. 그렇다면
A ➜ B 의 비용 <= A -> C 의 비용 이다. 이미 방문한 노드인 B에 대한 거리 배열 값이 바뀌려면, A ➜ C ➜ B의 값이 A ➜ B 의 값보다 작아야 하는데, 가능한가?
이미 A ➜ C의 비용이 A ➜ B보다 크거나 같은 상황인데, 거기에 양수 값이 추가된다면 절대 불가능하다.

1 ➜ 2 (비용 1)
1 ➜ 3 ➜ 2 (비용 3+K)

만약 해당 그래프에서 이미 방문한 2번 노드에 대한 최단 경로 값이 바뀌려면, 3+k < 1 즉 k < -2 여야 한다. k가 음수 값이 아닌 이상 방문한 노드에 대한 최단 경로 갱신은 이루어지지 않는다.

(2) 1번의 특징 때문에, 다익스트라 알고리즘은 가중치가 양의 정수인 경우만 사용할 수 있다.

만약 음의 정수가 허용되면, 이미 방문한 노드에 대한 최단 경로 갱신이 다시 일어날 가능성이 있고, 이는 그 전에 해왔더 계산과 비교 과정을 무의미하게 만들어, 처음부터 다시 최단 경로를 계산해야 한다. 이는 무한 루프에 빠지게 한다.