[알고리즘] 다익스트라 dijkstra - JAVA

 

알고리즘 문제를 푸는데, 노드 및 각 노드간의 cost (거리, 비용) 등을 주어져서 푸는 문제가 굉장히 많이 나온다.

 

물론 다익스트라가 무조건 답은 아니지만.. (dfs나 dp, 크루스칼이 답이될수도 있다.)

 

다익스트라 관점에서 생각해보는게 반드시 필요한 것같다.

 

다익스트라 알고리즘은 '그래프에서 한 지점에서 모든 지점으로의 최단 경로를 구하는 알고리즘' 이다.

- 대표적인 Greedy 알고리즘

 

다만 구현에 자꾸 까먹는게 있어서 정리를 해둬야 좋을것 같다.

 

 

- 구현 로직

1. 출발지점을 잡습니다.

2. distance 배열을 만든뒤 모든 배열을 MAX 값으로 세팅합니다.

3. distance 배열에서 최소값을 뽑은 뒤 그 점을 바탕으로 해서 distance 배열을 업데이트 합니다.

4. 3번 과정을 모든 지점을 방문할때 까지 반복합니다.

 

 

1. 배열을 이용한 다익스트라

import java.util.Arrays;
import java.util.Scanner;

public class 다익스트라 {
	//pq X 간선이 매우 많을 때 유리
	public static void main(String[] args) {
		Scanner sc = new Scanner(System.in);
		int V = sc.nextInt(); //정점의 개수
		int E = sc.nextInt(); //간선의 개수
		
		int[][] adj = new int[V][V];
		for (int i = 0; i < E; i++) {
			adj[sc.nextInt()][sc.nextInt()] = sc.nextInt();
		}
		int[] D = new int[V];
		Arrays.fill(D, Integer.MAX_VALUE);
		boolean[] check = new boolean[V];
		//dijkstra 시작점이 a정점이라면 D[a] = 0
		D[0] = 0;
		
		for (int i = 0; i < V-1; i++) {
			int min = Integer.MAX_VALUE; // 가장 작은 값을 기억할 변수
			int index = -1; //그 위치를 기억할 변수
		
			for (int j = 0; j < V; j++) {
				//아직 처리하지 않았으면서, 가장 짧은 거리면
				if(!check[j] && min > D[j]) {
					min = D[j];
					index = j;
				}
			}
			
			//새로운 친구로부터 갈수있는 경로들을 업데이트
			for (int j = 0; j < V; j++) {
				//!check[j], adj[index][j] != 0, D[index] + adj[index][j] < D[j]
				if(!check[j] && adj[index][j] != 0 && D[index] + adj[index][j] < D[j])
					D[j] = D[index] + adj[index][j];
			}
			//처리된놈으로 체크
			check[index] = true;
		}
		System.out.println(Arrays.toString(D));
	}

}

2. 우선순위 큐를 이용한 다익스트라

import java.util.*;

public class 다익스트라PQ {

	static class Edge implements Comparable<Edge>{
		int node, dis;
		public Edge(int node, int dis) {
			this.node = node;
			this.dis = dis;
		}
		@Override
		public int compareTo(Edge o) {
			return Integer.compare(this.dis,  o.dis);
		}
		@Override
		public String toString() {
			return dis + "";
		}
		
	}
	public static void main(String[] args) {
		Scanner sc = new Scanner(System.in);
		int V = sc.nextInt();
		int E = sc.nextInt();
		List<Edge>[] graph = new ArrayList[V];
		
		for (int i = 0; i < V; i++) {
			graph[i] = new ArrayList<>();
		}
		for (int i = 0; i < E; i++) {
			//첫번째가 출발지, 두번째가 도착지, 세번째가 가중치
			graph[sc.nextInt()].add(new Edge(sc.nextInt(), sc.nextInt()));
		}
		
		//dijkstra
		PriorityQueue<Edge> pq = new PriorityQueue<>();
		boolean[] visit = new boolean[V];
		Edge[] D = new Edge[V];
		
		//0번에서 출발하는 걸로
		for (int i = 0; i < V; i++) {
			//원하는 출발지
			if( i == 0) {
				//정점 0 번은 0으로 초기화
				D[i] = new Edge(i,0);
			}else {
				//나머지 정점은 최대값으로 초기화
				D[i] = new Edge(i, Integer.MAX_VALUE);
			}
			pq.add(D[i]);
		}
		while(!pq.isEmpty()) {
			Edge edge = pq.poll();
			if(edge.dis == Integer.MAX_VALUE) break;
			
			for (Edge next : graph[edge.node]) {
				// 방문했으면 x
				if(visit[next.node]) continue;
				// D[next.node]가 D[edge.node] + next.dis보다 더 크다면 갱신
				if(D[next.node].dis > D[edge.node].dis + next.dis) {
					D[next.node].dis = D[edge.node].dis + next.dis;
					
					//pq에 갱신된 next를 넣기위해 기존 요소를 제거하고 다시 삽입
					pq.remove(D[next.node]);
					pq.add(D[next.node]);
				}
			}
			//노드 방문체크
			visit[edge.node] = true;
		}
		System.out.println(Arrays.toString(D));
	}
}

출처: https://toastfactory.tistory.com/186 [이삭이의 토스트 공장]