최단 경로; 다익스트라(Dijkstra)

최단 경로의 개념

 

간선의 가중치가 있는 그래프에서 "두 정점 사이의 경로들 중"에 간선의 가중치의 합이 최소인 경로

1) 다익스트라(음의 가중치 허용하지 않음)

2) 벨만-포드(음의 가중치 허용함)

 

 

다익스트라의 개념

 

시작 정점에서 끝 정점까지 거리가 최소인 정점을 선택해가며 최단 경로를 구하는 방식

프림과 유사하나 당장의 가중치 한 개의 값이 아닌 "가중치의 합"을 고려해야 하는 알고리즘이다.

 

그래프에서 한 정점(노드)에서 다른 정점까지의 최단 경로를 구하는 알고리즘 중 하나이다. 이 과정에서 도착 정점 뿐만 아니라 모든 다른 정점까지 최단 경로로 방문하며 각 정점까지의 최단 경로를 모두 찾게 된다. 매번 최단 경로의 정점을 선택해 탐색을 반복하는 것이다.

 

다익스트라 동작 과정

 

1) 시작 정점 선택

2) 거리를 저장할 배열을 최댓값으로 초기화 => 시작 정점과 간선으로 연결된 다른 정점이 있다면 가중치를 넣어줌

3) 그 중 가장 가중치가 작은 간선으로 연결된 정점 선택 

4) 선택한 정점에서 연결될 수 있는 정점과 가중치 확인

5) 아직 방문하지 않은 점들이 가지고 있는 시작정점부터 해당 정점까지의 거리 값과 현재 정점에서 방문하지 않은 정점까지의 가중치의 합이 작다면 값 변경(갱신)

6)  목표 정점에 도달할 때까지 / 모든 정점을 돌 때 까지 반복 수행

 

 

다익스트라 구현

 

1) 인접행렬

2) 인접리스트 + 우선순위 큐 => 이걸로 풀자

 

인접행렬을 이용한 다익스트라 구현

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

public class Dijkstra {
	public static void main(String[] args) {
		Scanner sc = new Scanner("6 11\r\n" + "0 1 3\r\n" + "0 2 5\r\n" + "1 2 2\r\n" + "1 3 6\r\n" + "2 1 1\r\n"
				+ "2 4 6\r\n" + "2 3 4\r\n" + "3 4 2\r\n" + "3 5 3\r\n" + "4 0 3\r\n" + "4 5 6");
		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[] dist = new int[V];
		boolean[] visited = new boolean[V];
		//0번 정점에서 각 정점으로 최단거리가 얼만지 구하기
		for(int i = 0; i < V; i++) { //최대값으로 초기화
				dist[i] = 999;
		}
		dist[0] = 0;
		System.out.println(Arrays.toString(dist));
		//V-1개의 정점을 선택해가며 최단거리를 갱신할거임.
		for(int i = 0; i < V-1; i++) {
			//dist배열 중에서 가장 값이 작은 정점을 찾으시오.
			int minIdx = 0;
			int min = 999;
			for(int j = 0; j < V; j++) {
				if( !visited[j] && min > dist[j] ) {
					minIdx = j;
					min = dist[j];
				}
			}
			//모든 정점에 대해서 시작점에서 min위치를 들러서 다른 정점으로 가는 거리가 기존에 알던 dist보다 작으면 갱신.
			for(int j = 0; j < V; j++) {
				//min에서 검사하는 정점으로 갈 수 있는지 여부(간선이 있는지) adj[min][j] != 0
				//검사하는 정점까지 알고 있던 거리 dist[j]
				//min을 거쳐서 검사하는 정점까지 가는 거리 dist[min] + adj[min][j]
				if( adj[minIdx][j] != 0 && dist[minIdx] + adj[minIdx][j] < dist[j] )
					dist[j] = dist[minIdx] + adj[minIdx][j];
			}
			visited[minIdx] = true;
			System.out.println(Arrays.toString(dist));
		}
	}
}