개요
•
다이나믹 프로그래밍을 활용한 대표적인 최단 경로 알고리즘이다.
•
다익스트라는 특정한 정점에서 다른 모든 정점으로 가는 최단 경로를 알려준다. 다만 이때 음의 간선을 포함할 수 없다.
동작 단계
1.
출발 노드와 도착 노드를 설정한다.
•
ex) 1, 2 등
2.
최단 거리 테이블을 초기화한다.
•
ex) 1인 경우 다음과 같다.
7 | 0 | 10 | 15 | INF | INF |
3.
현재 위치한 노드의 인접 노드 중 방문하지 않은 노드를 구별하고 방문하지 않은 노드 중 거리가 가장 짧은 노드를 선택한다. 그 노드를 방문 처리한다.
•
ex) 위의 경우 인접 노드는 0, 2, 3이 존재하고 최단 경로인 7을 가진 0을 선택하고 0을 방문 처리한다.
4.
해당 노드를 거쳐 다른 노드로 넘어가는 간선 비용을 계산해 최단 거리 테이블을 업데이트 한다.
5.
3, 4번의 과정을 반복한다.
특징
•
다익스트라 알고리즘은 방문처리되지 않은 노드 중 최단 거리인 노드를 선택하는 과정을 반복한다.
•
각 단계마다 탐색 노드로 한 번 선택된 노드는 최단 거리를 갱신하고 그 뒤에는 더 작은 값으로 갱신되지 않는다.
코드
package graph;
import java.util.PriorityQueue;
public class Dijkstra {
public static void main(String[] args) {
int[][] graph = {
{0, 2, 5, 1, 0, 0},
{2, 0, 3, 2, 0, 0},
{5, 3, 0, 3, 1, 5},
{1, 2, 3, 0, 1, 0},
{0, 0, 1, 1, 0, 2},
{0, 0, 5, 0, 2, 0}
};
int start = 0;
int[] distance = dijkstra(graph, start);
for (int i = 0; i < distance.length; i++) {
System.out.println(start + " -> " + i + ": " + distance[i]);
}
}
public static int[] dijkstra(int[][] graph, int start) {
int n = graph.length;
int[] distance = new int[n];
boolean[] visited = new boolean[n];
for (int i = 0; i < n; i++) {
distance[i] = Integer.MAX_VALUE;
}
distance[start] = 0;
for (int i = 0; i < n - 1; i++) {
int minIndex = getMinIndex(distance, visited);
visited[minIndex] = true;
for (int j = 0; j < n; j++) {
if (!visited[j] && graph[minIndex][j] != 0 && distance[minIndex] != Integer.MAX_VALUE) {
distance[j] = Math.min(distance[j], distance[minIndex] + graph[minIndex][j]);
}
}
}
return distance;
}
// using priority queue
public static int getMinIndex(int[] distance, boolean[] visited) {
PriorityQueue<Node> pq = new PriorityQueue<>();
for (int i = 0; i < distance.length; i++) {
if (!visited[i]) {
pq.add(new Node(i, distance[i]));
}
}
return pq.poll().index;
}
public static class Node implements Comparable<Node> {
int index;
int distance;
public Node(int index, int distance) {
this.index = index;
this.distance = distance;
}
@Override
public int compareTo(Node o) {
return this.distance - o.distance;
}
}
}
Java
복사
