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

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

첫 정점을 기준으로 연결되어있는 정점을 추가해가며 최단거리를 갱신하는 기법이다.

 

어떤 문제를 풀 수 있는가?

한 정점에서 출발하여 그래프 내 다른 모든 정점까지의 가장 짧은 경로를 찾을 수 있다.

 

다익스트라 알고리즘 로직

• 첫 정점부터 각 노드간의 거리를 저장할 배열을 선언한 후, 첫 정점에서 인접 노드간의 거리를 계산하면서 첫 정점~해당 노드 간의 가장 짧은 거리를 해당 배열에 업데이트한다.
• <<우선순위 큐>> 를 이용한 다익스트라 알고리즘 (minHeap)

1. 첫 정점을 기준으로 배열을 선언하여 첫 정점에서 각 정점까지의 거리를 저장한다.
   1. 초기에 첫 정점의 거리는 0, 나머지는 무한대로 저장한다. (Integer.MAX_VALUE)
   2. 우선순위 큐에 삽입한다.
2. 우선순위 큐에서 노드를 꺼낸다.
   1. 꺼낸 노드의 인접한 노드들 각각에 대해 첫 정점에서 각 노드까지 가는 거리와 현재 배열에 저장되어있는 첫 정점에서 각 정점까지의 거리를 비교한다.
   2. 배열에 저장되어있는 거리보다 작을 경우, 배열의 값을 업데이트한다.
   3. 배열의 값을 업데이트된 경우에 해당 노드를 우선순위 큐에 넣는다.
      1. 만약 배열에 기록된 거리보다 더 긴 거리를 가진 경우에는 해당 노드와 인접한 노드간의 거리계산을 하지 않는다.
   4. 우선순위큐에 꺼낼 노드가 없을때까지 반복한다.

코드(그래프의 시작 정점과 다른 정점들간의 최단 거리구하기)

package week5;

import java.util.ArrayList;
import java.util.PriorityQueue;
import java.util.Scanner;
/*
TC1.
- 1부터 시작, 6개의 정점, 9개의 간선
1 6 9
1 2 8
1 3 1
1 4 2
3 2 5
3 4 2
4 5 3
4 6 5
5 6 1
6 1 5
*/
// 우선순위큐 사용 다익스트라 알고리즘
public class Dijkstra_queue {

	public static void main(String[] args) {
		Scanner sc = new Scanner(System.in);
		int start = sc.nextInt(); // 시작 정점
		int V = sc.nextInt(); // 정점개수
		int E = sc.nextInt(); // 간선개수
		
		//초기화
		ArrayList<Node>[] graph = new ArrayList[V+1];
		for (int i = 0; i <= V; i++) {
			graph[i] = new ArrayList<>();
		}
		
		//그래프 입력(출발지, 도착지, 가중치)
		for (int i = 0; i < E; i++) {
			graph[sc.nextInt()].add(new Node(sc.nextInt(), sc.nextInt()));
		}
		
		// dijkstra
		PriorityQueue<Node> pq = new PriorityQueue<>();
		int[] distance = new int[V+1]; // 시작점으로부터 해당 정점까지의 거리배열

		// 거리 배열 INF로 초기화
		for (int i = 0; i <= V; i++) {
			distance[i] = Integer.MAX_VALUE;
		}
		distance[start] = 0; // 출발지-> 출발지의 거리는 0
		pq.add(new Node(start, 0));
		
		while (!pq.isEmpty()) {
			Node edge = pq.poll();
			if (distance[edge.v] < edge.w) {
				continue;
				// 여기까지 오는 거리가, 이전에 이미 왔던 경로보다 크면 X
			}
			
			for (Node next : graph[edge.v]) {
				int next_distance = edge.w + next.w;
				// 현재 정점을 통해 가는 것이 더 아까울 경우
				if (next_distance < distance[next.v]) {
					distance[next.v] = next_distance;
					pq.add(new Node(next.v, next_distance));
				}
			}
		}
		
		// start정점으로부터 각 정점까지의 거리 출력
		for (int i = 1; i < distance.length; i++) {
			if (distance[i] == Integer.MAX_VALUE) {
				System.out.print("X ");
			} else {
				System.out.print(distance[i] + " ");
			}
		}	
	}
}
class Node implements Comparable<Node> {
	int v;
	int w;
	
	public Node(int v, int w) {
		this.v = v;
		this.w = w;
	}
	
	@Override
	public int compareTo(Node o) {
		return this.w - o.w; // +면 자리바꾸기 (오름차순)
	}
}

 

시간복잡도

• 다익스트라 알고리즘은 크게 다음 두 가지 과정을 거침
  • 과정1: 각 노드마다 인접한 간선들을 모두 검사하는 과정
  • 과정2: 우선순위 큐에 노드/거리 정보를 넣고 삭제(pop)하는 과정
• 각 과정별 시간 복잡도
  • 과정1: 각 노드는 최대 한 번씩 방문하므로 (첫 노드와 해당 노드간의 갈 수 있는 루트가 있는 경우만 해당), 그래프의 모든 간선은 최대 한 번씩 검사
    • 즉, 각 노드마다 인접한 간선들을 모두 검사하는 과정은 O(E) 시간이 걸림, E 는 간선(edge)의 약자
  • 과정2: 우선순위 큐에 가장 많은 노드, 거리 정보가 들어가는 경우, 우선순위 큐에 노드/거리 정보를 넣고, 삭제하는 과정이 최악의 시간이 걸림
    • 우선순위 큐에 가장 많은 노드, 거리 정보가 들어가는 시나리오는 그래프의 모든 간선이 검사될 때마다, 배열의 최단 거리가 갱신되고, 우선순위 큐에 노드/거리가 추가되는 것임
    • 이 때 추가는 각 간선마다 최대 한 번 일어날 수 있으므로, 최대 O(E)의 시간이 걸리고, O(E) 개의 노드/거리 정보에 대해 우선순위 큐를 유지하는 작업은 𝑂(𝑙𝑜𝑔𝐸)O(logE) 가 걸림
      • 따라서 해당 과정의 시간 복잡도는 𝑂(𝐸𝑙𝑜𝑔𝐸)

총 시간 복잡도

• 과정1 + 과정2 = O(E) + 𝑂(𝐸𝑙𝑜𝑔𝐸)O(ElogE) = 𝑂(𝐸+𝐸𝑙𝑜𝑔𝐸)=𝑂(𝐸𝑙𝑜𝑔𝐸)