[Algorithm] 다익스트라 알고리즘(자바)

다익스트라 : 그래프 내의 특정 정점에서 갈 수 있는 모든 정점들까지의 최단 경로를 구하는 알고리즘

 

특히, 다익스트라 알고리즘은 음수의 간선 가중치를 허용하지 않습니다.

한 정점에서 다른 정점으로 가는 최단 거리의 문제를 접한 경우 양의 가중치가 있으면 다익스트라 문제이다!!!!

 

---

다익스트라 과정

다음은 다익스트라 알고리즘을 통해 최단 경로를 구하는 과정입니다.

 

 

 

 

1. 초기 상태

초기 상태

저는 1번 정점부터 시작하겠습니다.

1	2	3	4	5
0	INF	INF	INF	INF

 

 

1-2 선택

1	2	3	4	5
0	4	INF	INF	INF

distance[2] > distance[1] + 4입니다.

이는 distance[2] = distance[1] + adjMatrix[1][2]를 의미합니다. 

 

 

 

1-4 선택

1	2	3	4	5
0	4	INF	10	INF

 

 

 

1-5 선택

1	2	3	4	5
0	4	INF	10	2

 

 

 

 

2. 5번 정점 선택

이제 1번 정점에서 가장 짧은 거리인 5번 정점을 살펴보겠습니다.

 

distance[4] > distance[5] + 5 이므로,

이는 distance[4] = distance[5] + adjMatrix[5][4] 으로 나타낼 수 있습니다.

 

1	2	3	4	5
0	4	INF	7	2

 

 

 

 

3. 2번 정점 선택

방문한 1, 5번 정점을 제외한 가장 짧은 거리를 가지고 있는 2번 정점을 선택하겠습니다.

이때, 2번 정점을 경유지로 삼아서 구할 수 있는 최단 거리를 구한다고 생각하면 될 것 같습니다.

 

1-3 선택

1	2	3	4	5
0	4	5	7	2

distance[3] > distance[2] + 1 이므로 이는 distance[3] = distance[2] + adjMatrix[2][3] 이 되므로 값이 갱신됩니다.

 

 

 

 

 

4. 3번 정점 선택

1, 2, 5번 정점을 제외한 정점 중에서 가장 거리가 짧은 3번 정점을 선택하겠습니다. 3번을 경유지로 삼아 구할 수 있는 모든 최단 거리를 구하면 됩니다.

 

3-4 선택

1	2	3	4	5
0	4	5	7	2

distance[4] > distance[3] + 2가 성립되지 않으므로 distance[4]는 갱신이 필요 없습니다.

끝으로 4번 정점을 제외한 모든 정점은 이미 처리되었으므로 4번 정점에 대한 과정은 거치지 않고 여기서 종료됩니다.

 

 

 

---

다익스트라 구현

 

1. 인접 행렬로 구현

코드 구현은 다음과 같습니다. 방문하지 않은 정점 중에서 최소 정점을 선택하고, 이 선택된 정점을 경유지로 해서 미방문 정점들로 가는 비용을 따져보고 기존 값보다 유리하다고 판단하면 갱신합니다.

public class DijkstraTest {
	public static void main(String[] args) throws NumberFormatException, IOException {
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		int V = Integer.parseInt(br.readLine());

		int[][] adjMatrix = new int[V][V];// 인접 행렬

		for (int i = 0; i < V; i++) {
			StringTokenizer st = new StringTokenizer(br.readLine(), " ");
			for (int j = 0; j < V; j++) {
				adjMatrix[i][j] = Integer.parseInt(st.nextToken());
			}
		}

		// start->end로 최단경로
		int start = 0;// 출발정점
		int end = V - 1;// 도착정점

		// 다익스트라 알고리즘에 필요한 자료구조
		int[] D = new int[V];// 출발지->자신으로 오는데 소요되는 최소비용
		boolean[] visited = new boolean[V];// 처리한 정점 여부
		
		Arrays.fill(D, Integer.MAX_VALUE);
		//출발정점 처리
		D[start] = 0;
		
		int min, minVertex;
		
		for (int i = 0; i < V; i++) {
			//step1. 미방문 정점 중 출발지에서 자신으로의 비용이 최소인 정점 선택
			//방문해야 하는 나머지 정점 중 출발지에서 가장 가까운 정점 찾기
			min = Integer.MAX_VALUE;
			minVertex = -1;
			
			for (int j = 0; j < V; j++) {
				if(!visited[j] && min > D[j]) {
					min = D[j];
					minVertex = j;
				}
			}
			
			//step2. 방문처리
			visited[minVertex] = true;
			
			//step3. 선택된 정점을 경유지로해서 미방문 정점들로 가는 비용을 따져보고 기존 최적해보다 유리하면 갱신
			for (int j = 0; j < V; j++) {
				if(!visited[j] && adjMatrix[minVertex][j] > 0) {
					if(D[j] > D[minVertex] + adjMatrix[minVertex][j]) {
						D[j] = D[minVertex] + adjMatrix[minVertex][j];//갱신 
					}
				}
			}
		}
		
		System.out.println(Arrays.toString(D));
		System.out.println(D[end]);//출발->도착 비용
	}
}

 

 

 

 

2. 인접 리스트로 구현

인접 리스트와 우선순위 큐를 사용하여 구현한 코드는 다음과 같습니다.

우선순위 큐를 통해 최소 정점을 뽑아서 그 정점을 경유지로 삼아 방문하지 않은 정점들로 가는 비용을 따져 보고 더 작다고 판단하면 갱신하게 됩니다. 

public class DijkstraTest2 {
	
	static class Node implements Comparable<Node>{
		int vertex, weight;

		public Node(int vertex, int weight) {
			this.vertex = vertex;
			this.weight = weight;
		}
		
		@Override
		public int compareTo(Node o) {
			return this.weight - o.weight;
		}
		
	}
	
	public static void main(String[] args) throws NumberFormatException, IOException {
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		StringTokenizer st = new StringTokenizer(br.readLine());
		
		int V = Integer.parseInt(st.nextToken());//정점 개수
		int E = Integer.parseInt(st.nextToken());//간선 개수 
		
		ArrayList<ArrayList<Node>> adjList = new ArrayList<ArrayList<Node>>();
		for (int i = 0; i < V; i++) {
			adjList.add(new ArrayList<Node>());
		}
		
		int[] distance = new int[V];//최단 거리 테이블
		Arrays.fill(distance, Integer.MAX_VALUE);
		distance[0] = 0;//시작 정점 초기화
		
		
		
		for (int i = 0; i < E; i++) {
			st = new StringTokenizer(br.readLine());
			int s = Integer.parseInt(st.nextToken());
			int e = Integer.parseInt(st.nextToken());
			int w = Integer.parseInt(st.nextToken());
			
			adjList.get(s).add(new Node(e, w));
		}/////입력 끝///////
		
		boolean[] visited = new boolean[V];
		PriorityQueue<Node> pq = new PriorityQueue<Node>();
		pq.offer(new Node(0, 0));//시작 정점
		
		while(!pq.isEmpty()) {
			Node node = pq.poll();
			int nowVertex = node.vertex;
			//int weight = node.weight;
			
			if(visited[nowVertex]) continue;
			visited[nowVertex] = true;
			
			for (Node adjNode : adjList.get(nowVertex)) {//선택한 현재 정점을 경유지로 삼아 이동하는 거리가 더 짧은 경우
				if(distance[adjNode.vertex] > distance[nowVertex] + adjNode.weight) {
					distance[adjNode.vertex] = distance[nowVertex] + adjNode.weight;
					pq.add(new Node(adjNode.vertex, distance[adjNode.vertex]));
				}
			}
		}
		
		System.out.println(distance[V-1]);
	}
}