1) 개념
한 정점(노드)에서 다른 정점(노드)까지의 최단 경로를 구하는 알고리즘
도착 정점 뿐만 아니라 다른 정점까지 최단경로로 방문하여 각 정점까지의 최단 경로를 모두 찾을 수 있음
탐욕기법을 사용한 알고리즘으로 MST 프림 알고리즘과 유사
2) 알고리즘 단계
D : 거리 계산을 위한 배열
U : 경로 배열
출발 노드(a)를 선택 후 a와 연결된 정점들에 대해 배열(D) 값을 가중치로 업데이트한다.
>> 다른 정점들은 아직 도달할 수 없는 정점이므로 배열 값 무한대인 상태(배열 초기값을 무한대로 설정해두기)이다.
D배열 중 거리가 가장 작으면서 U에 없는 정점(b) 선택한다.
a에서 b를 경유해서 갈 수 있는 정점 후보를 보고 그 때 가중치 값을 D에 UPDATE(D[b] +a[b][c])하고
D에 최솟값이면서 아직 방문하지 않은 정점을 선택해 모든 정점이 선택될 때까지 반복한다.
** 다익스트라가 음수가 불가능한 이유 **
음수가 되면 이미 선택된 정점들이 제외된 후 이미 선택된 점의 가중치가 음수여서 오히려 더 최단 경로가 되는 상황이 발생할 수 있다.
위 설명으로는 이해가 어려울 수 있으니 아래 그림을 예제로 하여 더 자세히 다익스트라 알고리즘 과정을 살펴보자.
다익스트라 알고리즘 구현을 위해 아래와 같은 배열들을 준비한다.
arr : 간선의 길이 값이 저장된 2차원 배열
dist : 다익스트라 알고리즘을 통해 최단 거리를 계산할 배열
visited : 방문한 노드를 체크할 배열
시작 노드 번호를 1이라 생각하고 최단거리를 계산하는 dist 배열을 채워보자.
(배열 Index의 경우 0번 index는 생략하도록 하겠다.)
1. dist 배열의 전체 값을 INF 값으로 채우되, 간선이 직접적으로 연결된 경우 그 간선의 길이 값을 넣어준다.
▶ 시작지점이 1이므로 1에서 1로 가는 값은 0이다.
▶ 2, 5번 노드는 1번 노드와 연결된 간선이 없으므로(아직 2번과 5번으로 가는 경로는 찾지 못했으므로) INF 이다.
▶ 3, 4번 노드는 1번 노드와 연결된 간선의 길이 값이 dist 배열에 채워진다.
2. 현재 방문하지 않은 노드 중에서 가장 비용이 적은 노드를 선택하고 그 노드와 연결된 간선들과 1번 노드에서 그 노드로 가는 dist값을 더하여 min 값으로 dist 배열을 갱신한다.
따라서 3번 노드가 선택되어 dist값을 갱신할 것이고, 이 때 visited[3] = true가 된다.
▶ 위 1번에서 가장 적은 값을 가진(Index 1 제외) 3번 노드가 선택된다.
▶ 3번 노드와 연결된 노드인 2번과 4번 index의 dist 배열 값을 갱신한다.
▶ 2번 노드 = min(dist[2], dist[3] + arr[3][2] ) : 원래 2번 노드까지 갈 때 소요되는 값과 1 -> 3 -> 2 순으로 3번 노드를 거쳐서 2
번 노드에 도달할 때의 값을 비교하여 더 작은 값으로 dist 값을 갱신한다.
즉, 1-> 3으로 가는 최소값인 dist[3]과 3번 노드에서 2번 노드로 가는 간선의 가중치인 arr[3][2] 값을 더한 값을 기존 dist[2]
와 비교하는 것이다.
▶ 4번도 위 2번 노드와 같은 과정을 거쳐 갱신한다.
3. visited 배열이 false인 index 중 value가 가장 작은 노드를 선택하여 위 과정을 또 반복한다.
따라서 3번 노드는 방문했으므로 남은 값 중 4번 노드가 선택될 것이다.
▶ 4번 노드와 연결된 노드 중 5번 노드의 최솟값이 갱신된다.
▶ dist[5] = min( dist[5], dist[4]+arr[4][5])
▶ 4번 노드의 visited 가 true로 바뀐다.
3. 3번과 같은 과정을 반복하면 최종적으로 아래와 같이 dist 배열이 완성된다.
3) 구현코드 예시
① for문 활용 : O(V^2)
위와 같은 과정의 다익스트라 알고리즘을 아래와 같이 구현해보았다.
위 예시에 한정된 코드가 아닌 일반적으로 입력값을 받고 start 지점부터 다익스트라 dist 배열을 채우고 end 지점의 값을 반환하는 코드이다.
public class Dijkstra {
public static void main(String[] args) throws NumberFormatException, IOExceaption{
//입력받기(인접행렬 방식)
BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
int V = Integer.parseInt(br.readLine());
Stringtokenizer st = new Stringtokenizer(br.readLine());
int start = Integer.parseInt(st.nextToken());
int end = Integer.parseInt(st.nextToken());
int[][] adjMatrix = new int[V][V];
for(int i=0; i<V; i++) {
st = new StringTokenizer(br.readLine(), " ");
for(int j=0; j<V; j++){
adjMatrix[i][j] = Integer.parseInt(st.nextToken());
}
}
//거리배열 값 무한대로 채우기
final int Inf = Integer.MAX_VALUE;
int[] dist = new int[V];
Arrays.fill(dist, Inf);
//시작지점만 0으로 두기
dist[start]=0;
//V개가 모두 다 골라지고 dist에는 출발 점에서 해당 정점으로 이동할 때의 최단 거리가 담길 것.
for(int c=0; c<V; c++){
//step1
current = -1;
min = Inf;
//처음이라면 시작지점이 current로 잡힐 것.
//아니라면 이전 단계에서 dist를 변경해둔 j 에서 잡힐 것.
for(int i=0; i<V; i++){
if(!visited[i] && min > distance[i] ) {
min = dist[i];
current = i;
}
}
//시작할 점이 없다면 끝.
if(current==-1) break;
//있다면 방문처리
visited[current] = true;
//step2
//방문하지 않은 점 중에서 현재 내가 있는 위치와 연결이 되어 있고,
//내가 이동할 때 드는 가중치 + 지금까지 쌓인 가중치보다 그 점까지 가는 가중치가 더 클 때
//내가 지금 이동할 가중치(min+adjMatrix[current][i]로 거리배열 값을 교체함
//그리고 이렇게 바뀐 점들 중 dist값이 최소인 점이 visited가 방문처리 될 점
for(int j=0; j<V;j++){
if(!visited[j] && adjMatrix[current][j] !=0
&& dist[j] > min +adjMatrix[current][j]){
dist[j] = min+adjMatirx[current][j];
}
}
System.out.println(dist[end] !=INF ? dist[end] : -1)
② PriorityQueue 활용 : O((V+E)logE)
PriorityQueue를 활용해서 구현해보자. 위 방법에서는 최소비용을 갖는 노드를 선택하고 주변 노드의 값을 갱신하는 방식이었다. 이는 dist배열에 갱신된 노드를 제외하고는 여전히 INF 값을 가져 굳이 고려해줄 필요가 없기 때문에 갱신하는 주변 노드의 값에 대해서만 최소비용을 갖는 노드를 선택해주면 되도록 우선순위 큐를 활용할 것이다.
즉, 우선순위 큐에 들어가는 노드의 수가 갱신할 주변 노드의 수를 의미하는 것이다.
위에서 구현한 방식은 for문으로 모든 노드를 돌기 때문에 O(V^2)의 시간복잡도를 가지게 된다. 하지만 이 방식은 우선순위 큐에 삽입하는 최대 횟수 = 간선의 개수이므로 최대 O((V+E)logE)의 시간복잡도를 가지게 된다.
여기서 O(ElogE)는 우선순위 큐에 삽입하는 시간복잡도이며 O(VlogE)는 우선순위 큐에서 추출해주는 연산에 대한 시간 복잡도이다.
이 방식의 경우 갱신될 경우에만 우선순위 큐에 넣기 때문에 visited 배열 또한 필요가 없다.
그럼 코드로 살펴보자.
public class Dijkstra {
static class Node {// 다음 노드의 인덱스와 가중치를 가진다
int idx
int cost;
Node(int idx, int cost) {
this.idx = idx;
this.cost = cost;
}
}
public static void main(String[] args) throws NumberFormatException, IOExceaption{
//입력받기(인접리스트 방식)
BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
int V = Integer.parseInt(br.readLine()); //정점 개수
int E = Integer.parseInt(br.readLine()); //간선 개수
//시작과 끝지점
Stringtokenizer st = new Stringtokenizer(br.readLine());
int start = Integer.parseInt(st.nextToken());
int end = Integer.parseInt(st.nextToken());
//인접리스트 생성
ArrayList<ArrayList<Node>> graph = new ArrayList<ArrayList<Node>>();
for (int i = 0; i < V + 1; i++) {
graph.add(new ArrayList<Node>());
}
for(int i=1; i<=E; i++) {
st = new StringTokenizer(br.readLine(), " ");
int s = Integer.parseInt(st.nextToken());
int e = Integer.parseInt(st.nextToken());
int cost = Integer.parseInt(st.nextToken());
graph.get(s).add(new Node(e,c));
}
//거리배열 값 무한대로 채우기
final int Inf = Integer.MAX_VALUE;
int[] dist = new int[V+1];
Arrays.fill(dist, Inf);
//가중치를 비교하는 PriorityQueue 선언
PriorityQueue<Node> pq = new PriorityQueue<Node> ((o1, o2) -> Integer.compare(o1.cost, o2.cost));
//시작노드에서 시작노드로 가는 값이 초기에 가장 짧은 비용 노드이므로 해당 노드를 넣어준다
pq.add(new Node(start, 0);
//시작지점만 0으로 두기
dist[start]=0;
while(!pq.isEmpty()){
Node current = pq.poll();
if(dist[current.idx] < current.cost) continue;
//선택된 노드와 연결된 주변 노드들 고려
for(int i=0; i<graph.get(current.idx).size(); i++){
Node next = graph.get(current.idx).get(i);
//pq에서 꺼낸 노드로 현재 보고 있는 current Node를 거쳐 가는 가중치가
//dist의 값보다 적다면 갱신하고 pq에 next Node 넣어주기
if(dist[next.idx] > current.cost+next.cost){
dist[next.idx] = current.cost + next.cost;
pq.add(new Node(next.idx, dist[next.idx]));
}
}
}
System.out.println(dist[end] !=INF ? dist[end] : -1)'Learning-log -CS > Data Structure & Algorithm' 카테고리의 다른 글
| (알고리즘/Java) 벨만-포드 (Bellman-Ford) 알고리즘 (0) | 2024.02.25 |
|---|---|
| 플로이드 워셜 알고리즘 (0) | 2023.07.05 |
| (자료구조 & 알고리즘 정리) 최소 비용 신장 트리, Kruskal, Prim (2023.06.25) (0) | 2023.06.25 |
| (자료구조 & 알고리즘 정리) 서로소집합, 유니온파인드 (2023.06.24) (0) | 2023.06.24 |
| (자료구조 & 알고리즘 정리) 그래프(DFS, BFS) (2023.06.23) (0) | 2023.06.23 |
