다익스트라

1. 다익스트라란?

2. 원리

1. 출발 정점으로부터 타 정점까지의 거리를 보여주는 dash board 만들기

2. 아직 방문하지 않은 정점들 중, 출발 정점에서 최소 비용으로 갈 수 있는 정점 방문 (방문 처리 필요)

3. 방문한 정점의 진출 간선을 활용하여 dash board 갱신

4. 모든 정점까지의 최단 거리가 판가름날 때까지 반복

3. 예시

(0) 대시보드 만들기

(1) 미방문 정점 중 최소 비용 경로 정점 방문

(2) 방문한 정점의 진출 간선으로 대시 보드 갱신

(3) 반복

4. 방문한 정점이 나중에 더 최소 비용으로 갱신되진 않을까?

• 그렇다면 다익스트라의 원리에 따라 가중치 비교에서 i > 2 라고 볼 수 있다.

• i와 K 모두 양수이기 때문에, 이후에 만나는 간선의 가중치인 i+K가 2보다 작아지는 것은 불가능하다.

5. 코드

(0) 간선 (Edge) 클래스

class Edge implements Comparable<Edge> {
	int vex;
	int cost;

	public Edge ( int vex, int cost) {
		this.vex = vex;
		this.cost = cost;
	}

	@Override
	public int compareTo(Edge ob) {
		return this.cost - ob.cost;
	}
}

• vex는 목적지 정점을 나타낸다.

• cost는 인접 리스트를 만들 때는 인접 정점 사이의 가중치를 나타내지만, 다익스트라에서는 출발정점에서부터 누적된 가중치 값을 나타낸다.
  (프림 알고리즘이랑은 다른점. 프림은 간선 가중치 자체만 저장하여 운용됨)

• compareTo() 함수는 다익스트라를 풀 때, 출발 정점에서부터 가장 최소 비용으로 갈 수 있는 정점을 고르기 위해 필요하다. 왜냐하면 PriorityQueue를 써서 풀 것이기 때문이다.

(1) 입력 받기 및 대시보드 초기화

static int [] dis;
static ArrayList<ArrayList<Edge>> lists = new ArrayList<ArrayList<Edge>>();

public static void main(String [] args) throws IOException {
	 BufferedReader br = new BufferedReader(new InputStreamReader(System.in));

	// 1. 대시보드는 정점을 모두 표현할 수 있게, 정점의 개수만큼 길이를 가지고, 처음에는 초기화가 되지 않았다는 의미로 2^31 - 1로 초기화
	int n = Integer.parseInt(br.readLine());
	dis = new int [n+1];
	Arrays.fill(dis, Integer.MAX_VALUE);

	// 2. 인접 리스트 초기화하기.
	for(int i = 0; i <= n; i++) {
		lists.add(new ArrayList<Edge>());
	}

	for(int i = 0; i < m; i++) {
		StringTokenizer st = new StringTokenizer (br.readLine());
		int start = Integer.parseInt(st.nextToken());
		int end = Integer.parseInt(st.nextToken()):
		int weight = Integer.parseInt(st.nextToken());
		lists.get(start).add(new Edge(end, weight));
	}

}

(2) 다익스트라 하기

public void dijstra(int start) {
	// 1. 가장 최소 비용 경로 뽑는 우선순위 큐
	PriorityQueue<Edge> pq = new PriorityQUeue<>();
	// 2. 시작점에 대한 초기화
	pq.offer(new Edge(v,0));
	dis[v] = 0;
	// 3. 실제 동작
	while(!pq.isEmpty()){
		Edge now = pq.poll();
		int vex = now.vex;
		int cost = now.cost;
		// (1) 이미 존재하는 최소 비용보다 크면 어짜피 방문할 필요가 없다.
		if(cost > dis[vex]) continue;
		// (2) 방문 지점의 진출 차선으로 대시보드 갱신
		for(Edge ob : lists.get(vex)) {
			if(dis[ob.vex] <= cost + ob.cost) continue;
			dis[ob.vex] = cost + ob.cost;
			pq.offer(new Edge(ob.vex, dis[ob.vex]));
		}
	}
}

A. 우선순위 큐를 쓰는 이유?

• 매 순회마다 우선순위큐에서 값을 빼면 되는데, 정점만큼 순회하니까 $$V$$

• 우선순위 큐의 경우, 정점으로 이루어진 heap 트리이다. 이때 루트값을 poll()빼고, 다시 max heap이든, min heap이든 복구하는 작업이 필요하다. 이때 최대 트리의 높이만큼 연산이 필요하므로 $$\log{V}$$의 연산이 필요하다.

B. 3번 동작의 (1)이 필요한 이유

6. 시간 복잡도

우선순위 큐(힙) + 인접 리스트를 썼을 경우

1. 매 반복마다 우선순위큐에서 '최소 경로로 갈 수 있는 미방문 정점' 을 뽑아낸다.
   해당 과정은 정점의 개수만큼 반복되는 루프 속에서 정점으로만 이루어진 Heap의 루트값을 반환하는 작업이다. 루트값을 뺀 후에 heap을 다시 최소 혹은 최대 힙으로 복구하는 과정이 필요하므로 최종적으로
   $$O(V \log{V})$$의 시간 복잡도가 든다.

2. 현 방문 정점에서 갈 수 있는 간선들을 모두 확인 후, 최단 경로 비용이 줄었으면 다시 큐에 삽입한다. 최단 경로 비용이 기존보다 줄어드는 현상을 완화라고 했을 때, 완화현상은 매 간선 확인마다 이루어질 수 있다.
   따라서 큐에 삽입하는 값은 간선의 개수만큼 이루어지며, 그때마다 힙을 정돈하는 연산은 logV만큼 필요하다 따라서 최종적으로 $$O(E \log{V})$$만큼의 시간복잡도가 든다.

Metadata

A. 모르는 것 정리

• 최단 경로
  : A → B 까지의 최단 경로는 A에서 B까지 최소 비용으로 가는 경로를 말한다.
  (최소 비용은 그래프의 성질에 따라 다른데, 가중치 그래프에서는 가중치 합계 비용, 가중치 없는 그래프에서는 간선의 개수이다.)