알고리즘 문제를 풀면서 다익스트라 알고리즘과 관련된 내용이 나왔다. 잘 모르는 부분이 있어서 기억하기 위해 정리하려 한다.

다익스트라 알고리즘

다익스트라 알고리즘은 그래프에서 출발점에서 도착점까지의 최단거리를 구할 때 사용하는 알고리즘이다.

주로 사용하는 변수 두개가 있다.

1
2
int[] distance = new int[n+1];
boolean[] visit = new boolean[n+1];

distance 배열에는 각각의 노드까지의 최단 거리가 저장된다.
visit 배열에는 각각의 노드를 방문했는지 여부를 표시하여 저장한다.

다익스트라 알고리즘의 순서는 다음과 같다.

  1. 최단 거리를 저장하는 distance 배열에는 처음에 나올 수 있는 가장 큰 값으로 초기화 해준다. 보통 Integer.MAX_VALUE 값으로 초기화 한다.
  2. 시작 노드의 거리를 0으로 표시한다. (이는 당연하다. 자기 자신까지의 거리는 0이기 때문.) 그리고 시작 노드의 visit 값을 true로 바꿔준다.
  3. 시작노드와 연결되어 있는 노드들의 distance 값을 갱신한다.
  4. 방문하지 않은 노드 중 distance 값이 최소인 노드 min_node를 찾는다.
  5. min_node의 visit 값을 true로 변경한다. 그리고 min_node와 연결된 노드들(방문하지 않은)의 distance 값을 갱신한다. 이때, min_node와 연결된 distance 값이 distance[min_node] + min_node와 그 노드의 거리 보다 큰 경우 distance 값을 distance[min_node]+ min_node와 그 노드의 거리로 갱신해준다.

4 ~ 5번을 모든 노드를 방문할 때까지 반복한다.

이렇게 순서를 설명했지만, 말로 설명하는 것보다는 그림을 보면서 이해하는 편이 더 빠를 것이다.

다음과 같은 그래프가 존재하고 시작점은 1이라고 가정한다. 그리고 간선에 표시되어 있는 값들은 가중치로 생각하면 된다.

  1. distance 값을 초기화 해준다.
node 1 2 3
distance 무한대 무한대 무한대
visit false false false
  1. 시작 노드가 1이므로 시작 노드의 distance와 visit 값을 변경해준다.
node 1 2 3
distance 0 무한대 무한대
visit true false false
  1. 시작 노드와 연결되어 있는 distance 값을 갱신한다.
node 1 2 3
distance 0 2 4
visit true false false

  1. 방문하지 않은 노드 중 distance가 최소인 값을 찾는다. 노드 2가 될 것이다.

  2. 최소인 노드2의 visit 값을 true로 변경한다.

node 1 2 3
distance 0 2 4
visit true true false

여기서는 노드 2와 연결되면서 방문하지 않은 노드들(여기서 노드 3)에 대해서 distance(3) > distance(2) + (2번과 3번 거리) 조건이 참이면 distance(3) = distance(2) + (2번과 3번 거리) 를 통해서 distance 값을 갱신한다.

3번까지의 거리는 4이고, 2번까지의 거리는 2 + 2와 3거리는 1이므로 4 > 2+1 이 성립된다. 따라서 distance(3)은 3으로 갱신된다.

node 1 2 3
distance 0 2 3
visit true true false

이처럼 노드 3의 distance 값은 더 최소인 값으로 갱신된다.

다익스트라 알고리즘과 관련된 문제는 알고스팟이라는 문제이다.

참고