기초 - 다익스트라

1. 다익스트라(V²)

• 음의 간선이 없을 때 정상적으로 작동.
• 그리디 알고리즘

방문하지 않은 노드 중에서 현재 최단 거리가 가장 짧은 노드를 확인해 그 노드에 대하여 비용을 계산하며 최단 거리를 갱신하는 알고리즘이다.

하지만 시간복잡도가 오래걸려 개선된 다익스트라를 사용하도록 한다.

2. 개선된 다익스트라(ElogV)

최단거리가 가장 짧은 노드를 PriorityQueue를 사용해서 바로 찾게 만들어 시간복잡도를 줄인다.

1. 먼저 출발 노드를 PriorityQueue에 넣어준다. 따라서 우선순위 큐에서 노드를 꺼낸 뒤에 해당 노드를 이미 처리한 적이 있다면 무시한다
   = 여기서 무시라는 것은 거리Arr에 있는 값들 보다 꺼낸 cost가 더 크다면 무시하라는 것이다.

위의 방법에 따라 즉 음수의 가중치도 해결할 수 있는 것이다. 단순한 방문 여부가 아니라 가중치가 더 짧을 경우 PriorityQueue에 삽입하는 것이기 때문에 이는 적절하다.

"다익스트라 : 음수 가중치를 구할 수도 있다." 참고 문헌

while(!pq.isEmpty()) {
	Node node = pq.poll();
	
	if(d[node.num] < node.cost) continue;
	
	for(Node nowNode : list.get(node.num)) {
		
		int costs = node.cost + nowNode.cost;
		if(costs < d[node.num]) {
			d[node.num] = costs;
			pq.add(new Node(costs, nowNode.num));
		}
	}
	
}

첫번째 턴 이후에 큐는 1번 노드와 연결된 노드 4, 2, 3번이 각각 거리가 적은 순서대로 들어가있을 것이다. 그렇게되면 처음 4번 노드가 나오게 되고 4번 노드에 연결된 5, 3번을 차례로 봐서 최단경로를 갱신해주는 알고리즘이다.

전체 코드

import java.util.*;

public class 다익스트라 {

	public static void main(String[] args) {
		int n = 6;
		
		PriorityQueue<Node> pq = new PriorityQueue<>();
		ArrayList<ArrayList<Node>> list = new ArrayList<>();
		int d[] = new int[n+1];
		
		for(int i = 0; i <= n; i++) {
			list.add(new ArrayList<>());
			d[i] = (int) 1e9;
		}
		
		// 1. list에다가 담기.
		
		pq.add(new Node(0, 1)); // 시작노드 넣어주기.
		
		while(!pq.isEmpty()) {
			Node node = pq.poll();
			
			if(d[node.num] < node.cost) continue;
			
			for(Node nowNode : list.get(node.num)) {
				
				int costs = node.cost + nowNode.cost;
				if(costs < d[node.num]) {
					d[node.num] = costs;
					pq.add(new Node(costs, nowNode.num));
				}
			}
			
		}
	}
	
	public static class Node implements Comparable<Node>{
		int cost;
		int num;
		
		public Node(int cost, int num) {
			this.cost = cost;
			this.num = num;
		}
		
		@Override
		public int compareTo(Node other) {
			return Integer.compare(this.cost, other.cost);
		}
	}

}