참고할 문제
다익스트라란?
다이나믹 프로그래밍을 활용한 대표적인 최단 경로 탐색 알고리즘이다.
다익스트라 알고리즘은 특정한 하나의 정점에서 다른 모든 정점으로 가는 최단 경로를 알려준다.
이 때 음의 간선은 포함할 수 없다.
동적프로그래밍과의 관계
다익스트라 알고리즘이 다이나믹 프로그래밍 문제인 이유는 최단 거리는 여러 개의 최단 거리로 이루어져 있기 때문이다.
작은 문제가 큰 문제의 부분집합에 속해있다고 할 수 있다.
기본적으로 다익스트라는 하나의 최단 거리를 구할 때 그 이전까지 구했던 최단 거리 정보를 그대로 사용한다는 특징이 있다.
다시 말해 다익스트라 알고리즘은 현재까지 알고 있던 최단 경로를 계속해서 갱신한다.
동작 과정
- 출발 노드를 설정한다.
- 출발 노드를 기준으로 각 노드의 최소 비용을 저장한다.
- 방문하지 않은 노드 중에서 가장 비용이 적은 노드를 선택한다.
- 해당 노드를 거쳐서 특정 노드로 가는 경우를 고려하여 최소 비용을 갱신한다.
- 3~4번을 반복한다.
기본 코드
선형 탐색 : 시간복잡도 = O(N^2)
정점의 갯수가 많은데 간선은 적은 경우 치명적일 정도로 비효율적이다.
int numberOfNode; // 노드 갯수
int min = Math.MAX
int[][] a // 전체 크래프
boolean[numberOfNode] visit // 방문한 노드
int[numberOfNode] index까지의 최단거리
int getSmallIndex(){ //최소 거리를 가지는 노드 반환
int min = Math.max
int index = 0;
for(int i = 0; i<numberOfNode;i++){
if(d[i]<min && !visit[i]){ //아직 방문 안된 노드들 중 해당 노드까지의 최단거리 중 가장 작은값 찾기
min = d[i];
index = i;
}
}
return index;
}
void dijkstra(int start){
for(int i = 0; i<numberOfNode; i++){
d[i] = a[start][i]; //일단 각 노드까지의 거리는 시작점에서의 거리
}
visit[start] = true;
for(int i = 0; i<numberOfNode-2;i++){ //총 계산은 node의 갯수 -2번 다시 반복
int current = getSmallIndex(); // 다음에 방문할 최단거리 index찾기
visit[current] = true;
for(int j = 0; j<numberOfNode;j++){
if(!visit[j]){
if(d[current]+a[current][j] <d[j]){ //아직 방문 안한 노드들 최단거리 업데이트 해주기
d[j] = d[current] + a[current][j];
}
}
}
}
} 우선순위 큐 : 시간복잡도 = O(N*logN)
기본적으로 다익스트라 알고리즘은 최소 비용을 갖는 노드를 선택하고 주변 노드의 값을 갱신했다.
그렇다면 비용을 나타내는 배열에서 갱신된 노드를 제외하고는 여전히 같은 값을 갖기 때문에 굳이 고려해줄 필요가 없다.
즉, 갱신하는 주변 노드의 값에 대해서만 다음 최소 비용을 갖는 노드를 선택해주면 된다
또한 Node클래스를 써서 시작점과 도착점을 간선별로 분리해서 코드를 작성하면 방향이 있는 간선을 다룰 수 있다.
static int V,E,start // V: 노드갯수, E: 간선갯수
static ArrayList<ArrayList<Node>> graph;
static class Node{
int idx, cost; // 다음 노드의 인덱스, 그 노드로 가는데 필요한 비용
}
public static void main(String[] args) throws IOException {
for (int i = 0; i < V + 1; i++) {
graph.add(new ArrayList<Node>());
}
for (int i = 0; i < E; i++) {
graph.get(startIndex).add(new Node(endIndex, cost));
}
// 다익스트라 알고리즘 초기화
int[] dist = new int[V + 1]; // 최소 비용을 저장할 배열
for (int i = 0; i < V + 1; i++) {
dist[i] = Integer.MAX_VALUE;
}
//노드를 최단시간 순으로 나열하도록 우선순위 큐 세팅하기
PriorityQueue<Node> q = new PriorityQueue<Node>((o1, o2) -> Integer.compare(o1.cost, o2.cost));
// 처음 시작점 세팅
q.offer(new Node(start, 0));
dist[start] = 0;
while (!q.isEmpty()) {
Node curNode = q.poll();
// 목표 정점이 꺼내 졌다면, 해당 노드까지는 최솟값 갱신이 완료 되었다는 것이 확정이다(다익스트라 알고리즘).
// 따라서, 반복문을 종료해도 되지만, 해당 코드는 시작 정점에 대하여 모든 정점으로의 최단 경로를 구하는 것을 가정한다.
// 아래 주석된 코드는 목표 정점이 구해졌다면 빠르게 탈출할 수 있는 조건이다.
// if (curNode.idx == end) {
// System.out.println(dist[curNode.idx]);
// return;
// }
// 해당 노드의 비용이 현재 dist배열에 기록된 내용보다 크다면
//이미 이 노드는 방문해서 dist에서의 최소비용이 변경되었다는 의미이므로 중복 방문 방지 생략
if (dist[curNode.idx] < curNode.cost) {
continue;
}
// 선택된 노드의 모든 주변 노드를 고려한다.
for (int i = 0; i < graph.get(curNode.idx).size(); i++) {
Node nxtNode = graph.get(curNode.idx).get(i);
if (dist[nxtNode.idx] > curNode.cost + nxtNode.cost) {
dist[nxtNode.idx] = curNode.cost + nxtNode.cost;
// 갱신된 경우에만 큐에 넣는다.
q.offer(new Node(nxtNode.idx, dist[nxtNode.idx]));
}
}
}
}다익스트라 활용 방안
일단 특정 지점에서 시작해서 특정 지점에서 끝나는 최단 거리 구하는 방법은 우리가 익히 알고 있듯이 BFS가 있지만 다익스트라도 활용할 수 있다.
따라서 최단거리, 최단시간을 구하는 문제는 무조건 BFS나 다익스트라를 먼저 떠올려야 한다.
BFS 와 다익스트라의 차이점
정점 V개 간선 E개가 존재한다고 하자.
BFS
시작점으로부터 어떤 지점까지 너비우선 탐색이다. 최단 경로를 구할 때 사용할 수 있다.
시간 복잡도 : O(E)
다익스트라
시작점으로부터 나머지 정점까지의 최단경로를 일괄로 구할때 더 용이하다.
시간 복잡도: O(ElogV) -> 인접리스트+우선순위 큐를 사용했을 때
최단 거리를 구하고자 할 때 사용전략
간선들 길이가 작을 때 다익스트라 알고리즘 대신 BFS 탐색을 이용해 최단거리를 구할지 고려하기
BFS는 모든 간선이 단위길이로 이루어졌을 때 방문하는 시점마다 해당 정점의 최단 경로를 구할 수 있기 때문에 다익스트라 알고리즘보다 빠른 경우가 있다.
즉, 주어진 간선들을 단위 길이의 간선으로 쪼개서 정점을 만든 후에 BFS를 돌면 모든 정점들의 최단 경로를 구할 수 있다.
