최단 경로
- 최단 경로 : 간선의 가중치가 있는 그래프에서 두 정점 사이의 경로들 중에 간선의 가중치의 합이 최소인 경로
- 하나의 시작 정점에서 끝 정점까지의 최단 경로→ 벨만-포드(Bellman-Ford) 알고리즘 : 음의 가중치를 허용
- → 다익스트라(dijkstra) 알고리즘 : 음의 가중치를 허용하지 않음
- 모든 정점들에 대한 최단 경로 : 플로이드-워샬(Floyd-Warshall) 알고리즘
Dijkstra 알고리즘 ( 다익스트라 알고리즘 - O(E log V))
- 시작 정점에서 거리가 최소인 정점을 선택해 나가면서 최단 경로를 구하는 방식
- 탐욕 기법을 사용한 알고리즘으로 MST의 프림 알고리즘과 매우 유사
- 우선순위 큐를 사용하여 효과적으로 최소 간선을 찾아 낼 수 있다. (입력 : O(log V), 출력 O(log V))
Dijkstra 구동 원리
Dijkstra Java Code
import java.io.BufferedReader;
import java.io.InputStreamReader;
import java.util.Arrays;
import java.util.StringTokenizer;
public class DijkstraTest {
public static void main(String[] args) throws Exception{
BufferedReader in = new BufferedReader(new InputStreamReader(System.in));
int V = Integer.parseInt(in.readLine());
int start = 0; // 출발점
int end = V-1; // 도착점
int adjMatrix[][] = new int[V][V]; // 인접행렬
StringTokenizer st = null;
for (int i = 0; i < V; i++) {
st = new StringTokenizer(in.readLine(), " ");
for (int j = 0; j < V; j++) {
adjMatrix[i][j] = Integer.parseInt(st.nextToken());
}
}
int[] distance = new int[V];
boolean[] visited = new boolean[V];
Arrays.fill(distance, Integer.MAX_VALUE);
distance[start] = 0;
// Priority Queue로 대체 가능하다. ->
// 매번 탐색하는 것보다 더 효율적일 수 있음 O(lg N)의 시간 복잡도 발생
for (int i = 0; i < V; i++) {
int min = Integer.MAX_VALUE;
int current = 0; // min 최소비용에 해당하는 정점 번호
// step 1 : 처리하지 않은 정점 중에 출발지에서 가장 가까운(최소비용) 정점 선택
for (int j = 0; j < V; j++) {
if(!visited[j] && min > distance[j]) {
min = distance[j];
current = j;
}
}
visited[current] = true;
// 고려한 정점이기 때문에 true로 만들어줌
if(current == end) break;
// 답으로 알고싶은 end를 찾으면 더이상 할 필요가 없다.
// step 2 : 선택된 current를 경유지로 하여 아직 처리하지 않은 다른 정점으로의 최소비용 따져본다.
for (int j = 0; j < V; j++) {
if(!visited[j] && adjMatrix[current][j] != 0 &&
distance[j] > min + adjMatrix[current][j]) {
distance[j] = min + adjMatrix[current][j];
}
}
}
System.out.println(distance[end]);
}
}
'Algorithms > 개념 정리' 카테고리의 다른 글
[문자열] 문자열 패턴 매칭 (0) | 2021.04.06 |
---|---|
[Graph] 최소 신장 트리(MST) (0) | 2021.03.29 |
[Graph] 서로소 집합 (0) | 2021.03.26 |
[Graph] Graph 탐색 (0) | 2021.03.25 |
[Graph] Graph 이론 (0) | 2021.03.24 |