[Java] Dijkstra 알고리즘

 

Dijkstra 알고리즘은 가중치와 방향이 있는 그래프에서 출발지에서 도착지까지의 최단거리를 구할 수 있는 알고리즘입니다.

이때, 주의할점은 음수인 가중치가 존재하면 안됩니다.

 

MST를 구하는 Prim 알고리즘과 매우 비슷한 과정으로 진행됩니다.

때문에, Dijkstra 알고리즘을 학습하면 Prim 알고리즘을 학습하실때 큰 도움이 됩니다!

[Java] Prim 알고리즘

 

(설명을 잘 못해서 코드를 보시는 게 빠를 수 있습니다.... ㅠ)

1. 정점 정보를 저장할 객체인 Edge 클래스(정점번호와 해당 정점까지의 가중치를 저장)를 만들고 해당 정점에 연결되는 인접한 정점만의 정보를 담기위해 ArrayList를 사용하여 배열(edgeList = new ArrayList[V + 1])을 만들어 줍니다. (ArrayList를 사용안하고 인접행렬을 사용해도됩니다!)

ex) 

예를들어, 위 이미지와 같이

1번 정점에는 2번, 3번 정점이

2번 정점에는 1번 정점이

3번 정점에는 1번 정점이 연결되어있습니다.

 

이를 위에서 ArrayList를 사용한 인접리스트로 표현하면

edgeList[1] = 2번의 edge 정보, 3의 edge 정보

edgeList[2] = 1번의 edge 정보

edgeList[3] = 1번의 edge 정보

가 저장됩니다.

 

이를 인접행렬로 표현하면

정점	1	2	3
1	0	2	5
2	2	0	0
3	0	0	5

와 같이 됩니다.

 

2. 최단거리를 구하기 위해 방문체크를 위한 visted 배열과 최소거리를 저장할 distance배열을 정점의 개수만큼 크기를 할당시켜줍니다. (이때, 정점이 1부터 시작하는경우 인덱스와 맞추어주기위해 +1을 했습니다.)

 

3. 이때, 최소거리를 구하는 것이므로 distance배열의 모든 인덱스를 큰 수로 초기화해줍니다. (자바의 경우, Arrays.fill(distance, Integer.MAX_VALUE); )

 

4. 시작점의 distance를 0으로 바꾸어줍니다.

 

5. 출발지에서 도착지로가는 최소경로를 모든 정점을 살피며 찾아야하므로 정점의 개수만큼 반복문을 돌립니다.

   5-1. distance를 조사하면서 방문하지 않았으면서 가장 짧은 거리와 해당 인덱스를 저장합니다.

   (이 과정에서 힙을 사용하면 더욱 빠르게 처리가 가능합니다.)

   5-2. 가장 짧은 거리를 갖고있는 정점을 방문처리를 합니다.

   (만약, 도착지까지만 구하고 싶다면 이 과정에서 if문을 하나 더 추가하여 선택된 정점이 도착지라면 break를 하여 경로탐색을 종료하게합니다.)

   5-3. 가장 짧은 거리를 갖고있는 정점과 연결되어있는 모든 정점을 조사합니다.

         5-3-1. 조사를 하면서 방문하지 않았고 현재 가장 짧은 거리를 갖고있는 정점과 연결되어있는 해당 정점의 distance값보다 현재 정점까지의 최단 경로에 해당 정점으로 가는 가중치를 더한 값이 더 작다면 해당 정점으로 가는 최단거리가 되므로 distance의 값을 가중치로 업데이트하여 최소 거리를 만듭니다.

         (이때, 인접 행렬의 경우 추가적으로 현재 정점과 해당 정점이 연결되있는지 여부를 확인해야 하므로 if문에 만약 인접행렬의 이름이 adj라면 adj[cur][j] > 0 이라는 조건을 추가해야 합니다.)

         5-3-2. 5번을 이어서 반복합니다.

 

위 과정을 거치면 최단거리를 구할 수 있습니다.

 

아래 코드같은 경우는 출발점에서 다른 모든 점까지의 최단거리를 구하는 코드이기때문에 코드 마지막 부분에 갈 수 없는 정점이라면 "INF"를 출력하게했습니다.

---

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.ArrayList;
import java.util.Arrays;
import java.util.List;
import java.util.StringTokenizer;

public class Dijkstra {
	public static class Edge {
		int v, weight;

		public Edge(int v, int weight) {
			super();
			this.v = v;
			this.weight = weight;
		}
	}
	
	public static int V, E, K;
	public static boolean[] visited;
	public static int[] distance;
	public static List<Edge>[] edgeList;
	public static void main(String[] args) throws IOException {
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		StringTokenizer st = new StringTokenizer(br.readLine(), " ");
		
        // 정점의 개수
		V = Integer.parseInt(st.nextToken());
        // 간선의 개수
		E = Integer.parseInt(st.nextToken());
        // 출발지점
		K = Integer.parseInt(br.readLine());
		
		visited = new boolean[V + 1];
		distance = new int[V + 1];
		edgeList = new ArrayList[V + 1];
		
		// 0도 최단경로를 구하는 과정에서 들어갈 수 있으므로 초기화
        // 에러 방지
		for (int i = 0; i <= V; ++i) {
			edgeList[i] = new ArrayList<Edge>();
		}
		
		// 주의!! 최단 경로는 방향이있다!
		for (int i = 0; i < E; ++i) {
			st = new StringTokenizer(br.readLine(), " ");
			edgeList[Integer.parseInt(st.nextToken())].add(new Edge(Integer.parseInt(st.nextToken()), Integer.parseInt(st.nextToken())));
		}
		
		Arrays.fill(distance, Integer.MAX_VALUE);
		distance[K] = 0;
		
		for (int i = 1; i <= V; ++i) {
			int min = Integer.MAX_VALUE;
			int cur = 0;
			
			for (int j = 1; j <= V; ++j) {
				if (!visited[j] && min > distance[j]) {
					min = distance[j];
					cur = j;
				}
			}
			
			visited[cur] = true;
			// 출발지에서 모든점을 조사하므로 종료지점은 없어도된다.
            //if (cur == dest) {
			//	break;
			//}
			
			for (Edge e : edgeList[cur]) {
				if (!visited[e.v] && distance[e.v] > min + e.weight) {
					distance[e.v] = min + e.weight;
				}
			}
		}
		
		StringBuilder sb = new StringBuilder();
		for (int i = 1; i <= V; ++i) {
			sb.append((distance[i] == Integer.MAX_VALUE) ? "INF" : distance[i]).append("\n");
		}
		System.out.println(sb);
	}
}