[알고리즘] 최단경로 - Dijkstra 알고리즘

 

 

 

 Dijkstra 

최단경로

최단 경로 알고리즘 (Shortest Path)
: 시작 정점에서 끝 정점까지 가장 짧은 경로를 찾는 알고리즘

'길 찾기' 문제라고도 불립니다.

최단 경로 알고리즘은 보통 그래프로 표현되고, 해결 알고리즘은 3가지가 있습니다.

1. 다익스트라 알고리즘
2. 플로이드-워셜 알고리즘
3. 벨만-포드 알고리즘

오늘 포스팅에서는 다익스트라 알고리즘에 대해서 알아보도록 하겠습니다.

 

 

Dijkstra 특징

1. 시작 노드 설정하고 이를 우선순위 큐에 넣는다.
2. 우선순위 큐에서 시작 노드에서부터 가장 거리 비용이 짧은 노드를 꺼낸다.
3. 꺼낸 노드로부터 갈 수 있는 방문하지 않은 모든 노드의 거리비용을 계산한다.
4. 만약 해당 거리 비용이 테이블의 거리비용보다 짧다면 갱신한다.

 

 

Dijkstra 예제

우선 cost 테이블을 초기화를 해주어야 합니다. 최소값이 갱신될 수 있도록 큰 값으로 초기화를 해줍니다.

다익스트라는 유방향 그래프에서도 사용이 가능합니다.

여기서 cost[cur] 은 현재 노드를 의미 합니다. 즉 방문할 수 있는 노드를 탐색하는 노드 입니다.

a[i] 는 from(현재노드) -> to(방문하고자 하는 노드) 의 거리 비용을 의미합니다.

즉슨 1 -> 2 의 거리 비용은 2가 됩니다. 3 -> 5 은 6이 됩니다.

시작 노드를 설정해줍니다. 시작노드는 1로 설정하였습니다. 따라서 cost[cur] 은 1이 됩니다.

시작 노드에서 방문할 수 있는 모든 노드까지의 거리 비용을 계산합니다.

모든 노드가 갱신될 수 있으므로 계산한 거리 비용을 테이블에 저장합니다.

테이블에서 거리 비용이 제일 짧은 2번 노드를 그 다음에 방문합니다.

(만약 거리 비용이 같다면 보통 노드 번호가 작은 노드 부터 방문합니다.)

1번 시작 노드부터 -> 2번 노드를 거쳐 -> 방문할 수 있는 노드 까지의 거리 비용을 계산합니다.

cost[cur] 은 2번 노드가 되고 cost[cur] + a[i] 중에서 테이블 보다 작은 값이 없으므로 갱신이 일어나지 않습니다.

짧은 거리인 3번 노드를 방문합니다.

1번 노드 -> 3번 노드 -> 방문할 수 있는 모든 노드까지의 거리 비용을 계산합니다.

여기서는 1 -> 3 -> 5 가 1 -> 5 보다 거리 비용이 작으므로 테이블에 갱신이 됩니다.

cost[cur] 은 4번 노드가 됩니다. 4번 노드가 현재 노드일 때는 갱신되는 값이 없습니다.

5번 노드도 마찬가지입니다.

이렇게 모든 노드를 방문하게 되어 cost 배열을 만들 수 있게 됩니다.

따라서 만약 끝 정점을 5번이라고 지정한다면, 1번 노드에서 5번 노드까지의 최단 경로는 8이 됩니다.

 

 

Dijkstra 알고리즘 input.txt

3
5
0 2 2 5 9
2 0 3 4 8
2 3 0 7 6
5 4 7 0 5
9 8 6 5 0
6
0 3 5 0 0 0
0 0 2 6 0 0
0 1 0 4 6 0
0 0 0 0 2 3
3 0 0 0 0 6
0 0 0 0 0 0
10
0 4 6 0 0 0 0 0 0 0
0 0 0 9 8 0 0 0 0 0
0 3 0 0 2 3 0 0 0 0
0 0 0 0 0 0 6 0 0 0
0 0 0 2 0 1 3 7 0 0 
0 0 0 0 0 0 0 4 8 0
0 0 0 0 0 0 0 0 0 13
0 0 0 0 0 0 0 0 0 9
0 0 0 0 0 0 0 0 0 4
0 0 0 0 0 0 0 0 0 0

 

 

Dijkstra 알고리즘 코드

package first.p05;


import java.io.BufferedReader;
import java.io.FileInputStream;
import java.io.InputStreamReader;
import java.util.PriorityQueue;
import java.util.StringTokenizer;


public class DijkstraTest {
	static final int INF = Integer.MAX_VALUE;
	static int ans, T, N;
	static int[][] matrix; // 인접 행렬
	static int[] cost; // 시작정점과의 거리 비용
	static boolean[] visit;

	static PriorityQueue<Edge> pq = new PriorityQueue<>((e1, e2) -> e1.cost - e2.cost);


	public static void main(String[] args) throws Exception {
		System.setIn(new FileInputStream("src/first/p05/input/dijkstra.txt"));
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));

		T = Integer.parseInt(br.readLine());
		for (int t = 1; t <= T; t++) {
			N = Integer.parseInt(br.readLine());

			// 초기화
			ans = 0;
			matrix = new int[N][N];
			cost = new int[N];
			visit = new boolean[N];
			for (int i = 0; i < N; i++) {
				StringTokenizer st = new StringTokenizer(br.readLine());
				for (int j = 0; j < N; j++) matrix[i][j] = Integer.parseInt(st.nextToken());
				cost[i] = INF;
			}

			// for (int i = 0; i < N; i++) System.out.println(Arrays.toString(matrix[i]));

			// 다익스트라
			dijkstra(0);

			// 출력
			ans = cost[N - 1];
			System.out.println("#" + t + " " + ans);

		}

	} // end main


	private static void dijkstra(int k) {
		// 시작 노드
		cost[k] = 0;
		pq.offer(new Edge(k, 0));

		while (!pq.isEmpty()) {
			// 거리 비용이 가장 짧은 노드 꺼내기
			Edge edge = pq.poll();
			int cur = edge.to;

			// 만약 방문한 정점이라면 skip
			if (visit[cur]) continue;

			visit[cur] = true; // 방문 처리

			for (int i = 0; i < N; i++) {
				// 현재 노드에서 -> 갈 수 있는 모든 노드
				int ncost = cost[cur] + matrix[cur][i];

				if (visit[i]) continue;
				if (matrix[cur][i] == 0) continue;

				// 위 경로가 갱신되어져 있는 거리비용보다 작다면 새롭게 갱신된다.
				if (ncost < cost[i]) {
					cost[i] = ncost;
					pq.offer(new Edge(i, cost[i]));
				}

			}

		}

	} // end dijkstra


	static class Edge {
		int to;
		int cost;


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

	} // end Edge
}

출력

시작 노드를 설정합니다.

그리고나서 해당 노드를 우선순위 큐에 넣습니다.

우선순위 큐에서 비용이 가장 작은 것을 꺼냅니다. 해당 노드가 현재 노드가 됩니다.

현재 노드에서 방문할 수 있는 노드를 탐색합니다.

만약 새로운 cost 값이 (cost[cur] + matrix[cur][i]) 이전에 있던 cost 값 (cost[i]) 보다 작다면 갱신을 합니다.

그리고 나서 해당 거리 비용 간선을 우선순위 큐에 추가합니다.

 

 

 

 

 

 

 

# 다익스트라 알고리즘 # 다익스트라 java # 다익스트라 인접행렬

---