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

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

 - 그래프 상의 한 노드에서 다른 모든 노드까지의 최단 거리를 구할 때 유용하게 사용되는 알고리즘이다.

 - 노드와 노드 사이의 간선의 가중치가 0 이상의 정수일 때만 사용이 가능하다.

---

다익스트라 알고리즘의 동작 과정

1단계

 

노드	1	2	3	4	5	6
거리	0	2	5	1	INF	INF

 

 - 출발 노드인 1을 기준으로 인접한 노드인 2, 3, 4 노드에 대한 최단 거리 테이블을 만들어 준다.
 - 인접하지 않은 노드인 경우 무한으로 표시한다.

 

2단계

 

노드	1	2	3	4	5	6
거리	0	2	1+3=4	1	1+1=2	INF

 

 - 노드 1과 인접한 노드들 중 최단 거리가 가장 짧은 노드인 4번으로 진행한다.
 - 노드 4와 인접한 노드는 3, 5 노드이고, 이 노드까지의 최단 거리와 기존의 최단 거리 테이블의 값과 비교하여 더 짧은 거리로 갱신해준다.

 

3단계

 

노드	1	2	3	4	5	6
거리	0	2	4	1	2	INF

 

 - 다음은 방문하지 않은 노드들 중 가장 짧은 노드인 2번 노드로 진행한다.
 - 노드 2와 인접한 노드는 3, 4 노드이고, 이 노드까지의 최단 거리와 기존의 최단 거리 테이블의 값과 비교하여 더 짧은 거리로 갱신해준다.
 - 기존의 최단 거리 테이블의 값이 더 적으므로 갱신할 필요가 없다.

 

4단계

 

노드	1	2	3	4	5	6
거리	0	2	2+1=3	1	2	2+2=4

 

 - 다음은 방문하지 않은 노드들 중 가장 짧은 노드인 5번 노드를 선택하고, 최단 거리 테이블 갱신 과정을 반복한다.

 

5단계

 - 다음으로는 3번 노드를 선택하고, 3번 노드의 인접 노드인 6번 노드의 거리가 기존의 최단 거리보다 크므로 갱신하지 않는다.

 

6단계

 - 마지막으로, 6번 노드는 인접한 노드가 없기 때문에 알고리즘이 종료된다.

---

구현 방법

노드에 대한 정보

static class Node implements Comparable<Node> {
	int number;
	int weight;

	Node(int number, int weight) {
		this.number = number;
		this.weight = weight;
	}

	@Override
	public int compareTo(Node o) {
		return this.weight - o.weight;
	}
}

 - 노드에 대한 정보를 정의한 코드이다.
 - 각 노드는 번호와 가중치를 가지고 있으며, 우선순위 큐의 활용을 위해 가중치의 오름차순으로 compareTo() 메서드를 재정의하였다.

 

다익스트라 알고리즘의 사전 준비

static ArrayList<Node>[] arr;
static int[] distance;
static boolean[] visited;

 - arr는 각 노드들의 연결관계를 나타내는 변수이며, ArrayList의 자료구조로 선언하였다.
 - distance는 시작 노드에서 각 노드까지의 최단 거리를 저장하는 배열이다.
 - visited는 각 노드의 방문 여부를 저장하는 배열이다.

 

우선순위 큐를 이용한 다익스트라 알고리즘의 구현

static void dijkstra(int start) {
	PriorityQueue<Node> queue = new PriorityQueue<>();

	Arrays.fill(distance, Integer.MAX_VALUE);

	distance[start] = 0;
	queue.add(new Node(start, 0));

	while (!queue.isEmpty()) {
		Node current = queue.poll();

		if (visited[current.number] == false)
			visited[current.number] = true;
		else
			continue;

		for (int i = 0; i < arr[current.number].size(); i++) {
			Node next = arr[current.number].get(i);

			if (distance[current.number] + next.weight < distance[next.number]) {
				distance[next.number] = distance[current.number] + next.weight;

				queue.add(new Node(next.number, distance[next.number]));
			}
		}
	}
}

 - 우선순위 큐를 선언한 후, distance[] 배열을 정수의 최대치로 초기화한다.
 - 그 후, 시작 노드의 최단거리를 0으로 초기화를 하고, 시작 노드를 우선순위 큐에 삽입한다.
 - 우선순위 큐에서 가장 낮은 가중치를 가진 노드를 꺼내어 방문 여부를 확인한다.
 - 방문하지 않은 노드라면, 해당 노드와 인접한 노드들의 가중치와 기존의 가중치를 비교하여 더 낮은 값이라면 새로운 값으로 갱신한다.
 - 위 과정을 우선순위 큐가 빈 상태일 때까지 반복한다.

---

GitHub - qlsdud0604/algorithm-study: 자료구조 및 알고리즘 공부 기록 공간