참고
다익스트라(Dijkstra)
NOTE
한 정점(노드)에서 다른 정점까지의 최단 경로를 구하는 알고리즘!
이러한 그래프에서 1번 노드가 5번으로 가기위한 최단거리를 구함
•
탐욕 알고리즘 방식으로 동작한다.
◦
매 단계에서 가장 비용이 낮은 노드를 선택해 최적의 해결책을 찾는다.
•
단일 출발점
◦
하나의 지점에서 모든 다른 지점까지의 최단경로를 찾는다.
•
경로 정보
◦
노드까지의 최단경로 뿐만 아니라, 해당 최단 경로를 얻는데 사용된 경로 정보도 제공한다.
•
장점
◦
최단 거리를 알 수 있다.
◦
최단 거리 뿐만 아니라, 쵣나 경로를 얻는데 사용된 정보도 제공한다.
•
단점
◦
음의 경우의 수를 포함하지 않는다
순차탐색 구현방법
NOTE
방문하지 않는 노드 중 가장 작은 노드를 선택해 다음 탐색 노드로 삼는다!
1번 노드에서 출발하는 경우 2,4 노드 중에서 하나를 선택하는데 최단거리인 4를 선택
public void dijkstra(int v){
// 시작지점
int v = 0;
// 거리, 방문여부, 그래
int[] dist = new int[n];
boolean[] visited = new boolean[n];
int[][] graph = new int[n][n];
// 그래프 초기화 과정(도달하지 못하는 노드는 무한대로 표기)
for(int i=0; i<n; i++){
for(int j=0; j<n; j++){
graph[i][j] = Integer.MAX_VALUE;
}
}
// 그래프 간선 입력
for(int[] e : edge){
graph[e[0]-1][e[1]-1] = 1;
graph[e[1]-1][e[0]-1] = 1;
}
// 거리 초기화, 시작노드 설정
Arrays.fill(dist, Integer.MAX_VALUE);
dist[v] = 0;
visited[v] = true;
// 시작노드 간선을 거리에 추가
for(int i=0; i<n; i++){
if(!visited[i] && graph[v][i] != Integer.MAX_VALUE)
dist[i] = graph[v][i];
}
// 모든 정점들을 순회하면서 최단거리 구
for(int i=0; i<n; i++){
int min_index = -1;
int min = Integer.MAX_VALUE;
// 현재 방문하지 않은 정점중 최단거리 노드 선택
for(int j=0; j<n; j++){
if(!visited[j] && dist[j] < min){
min = dist[j];
min_index = j;
}
}
if(min_index == -1) continue;
// 최단거리의 노드 방문체크
visited[min_index] = true;
for(int j=0; j<n; j++){
if(visited[j] || graph[min_index][j] == Integer.MAX_VALUE) continue;
// v -> j VS v -> min_index -> j 비교한다.
if(dist[min_index] + graph[min_index][j] < dist[j])
dist[j] = dist[min_index] + graph[min_index][j];
}
}
}
Java
복사
어떤 정점이 최단거리로 갈 수 있는가를 판단한다.
•
시간복잡도 : O(V^2)
◦
정점의 개수가 N이라고 한다.
◦
노드마다 최소 거리 값을 가지는 순차 탐색이 진행되므로
(N -1) * N 만큼의 시간이 걸린다.
다익스트라 - 우선순위 큐 구현방법
NOTE
우선순위 큐를 사용해 매번 루트 노드가 최소 거리를 가지는 노드로 구성되게 한다!
인접행렬과 다르게, 거리값에 따라 자동으로 정렬되어 바로 4번을 선택할 수 있다
public int solution(int n, int[][] edge) {
int v = 0;
int[] dist = new int[n];
boolean[] visited = new boolean[n];
// 2차원 배열말고 2차원 리스트를 사용한다. (메모리 절약)
List<List<Integer>> graph = new ArrayList<>();
for (int i = 0; i < n; i++) {
graph.add(new ArrayList<>());
}
// 우선순위 큐 사용
PriorityQueue<Node> pq = new PriorityQueue<Node>((n1,n2) -> Integer.compare(n1.weight, n2.weight));
// 그래프 초기화
for (int[] e : edge) {
graph.get(e[0] - 1).add(e[1] - 1);
graph.get(e[1] - 1).add(e[0] - 1);
}
// 거리 초기화, 시작정점 입력
Arrays.fill(dist, Integer.MAX_VALUE);
dist[v] = 0;
pq.add(new Node(0, v, v));
// 다익스트라 알고리즘 시작
while (!pq.isEmpty()) {
Node node = pq.poll();
int curr = node.dest;
if (visited[curr]) continue; // 방문한 노드면 생략
visited[curr] = true;
// v -> j VS v -> min_index -> j 비교한다.
for (int neighbor : graph.get(curr)) {
if (dist[curr] + 1 < dist[neighbor]) {
dist[neighbor] = dist[curr] + 1;
pq.add(new Node(dist[neighbor], curr, neighbor));
}
}
}
}
Java
복사
우선순위 큐로 다익스트라를 진행하는 방식
•
시간복잡도 : O(V log V)
◦
우선순위 큐에서 꺼낸 노드는 연결된 노드만 탐색하므로 E만큼 반복한다.
◦
하나의 간선에 대해서는 O(log E)이고 E는 항상 V^2보다 작다
▪
log V^2 = 2 log V
▪
2 log V ⇒ O(log V)