다익스트라(Dijkstra) 알고리즘은 그래프 상에서 시작 정점부터 나머지 각 정점까지의 최단거리를 계산하는 알고리즘이다. 다익스트라 알고리즘은 그래프의 어느 간선의 가중치라도 음수가 있으면 안된다. (가중치에 음수가 포함될 수 있으면 벨만-포드 알고리즘)
다익스트라 알고리즘을 구현하기 위해서는 다음과 같은 과정을 반복하면 된다.
- 방문하지 않은 정점 중 가장 가중치 값이 작은 정점을 방문한다. (처음엔 시작 정점 방문)
- 해당 정점을 거쳐서 갈 수 있는 정점의 거리가 이전에 기록한 값보다 작다면 그 거리를 갱신한다.
public class Dijkstra {
public static void main(String[] args) throws IOException {
BufferedReader bufferedReader = new BufferedReader(new InputStreamReader(System.in));
int v = Integer.parseInt(bufferedReader.readLine());
int[][] adjMatrix = new int[v][v];
int start = 0;
StringTokenizer stringTokenizer = null;
for (int i = 0; i < v; i++) {
stringTokenizer = new StringTokenizer(bufferedReader.readLine());
for (int j = 0; j < v; j++) {
adjMatrix[i][j] = Integer.parseInt(stringTokenizer.nextToken());
}
}
int[] distance = new int[v]; // 출발지에서 자신으로 오는 최소비용
boolean[] visited = new boolean[v]; // 최소비용 확정여부
Arrays.fill(distance, Integer.MAX_VALUE);
distance[start] = 0; // 시작점 0으로
for (int i = 0; i < v; i++) {
// step 01. 최소비용이 확정되지 않은 정점 중 최소비용의 정점 선택
int min = Integer.MAX_VALUE;
int current = 0;
for (int j = 0; j < v; j++) {
if (!visited[j] && min > distance[j]) {
min = distance[j];
current = j;
}
}
visited[current] = true;
// step 02. 선택된 정점을 경유지로 하여 아직 최소비용이 확정되지 않은 다른 정점의 최소비용을 고려
for (int j = 0; j < v; j++) {
if (!visited[j] && adjMatrix[current][j] != 0 && distance[j] > distance[current]+adjMatrix[current][j]) {
distance[j] = distance[current] + adjMatrix[current][j];
}
}
}
System.out.println(Arrays.toString(distance));
}
}public class DijkstraWithPQ {
static class Vertex implements Comparable<Vertex> {
int no; // 정점 번호
int minDistance; // 출발지에서 자신으로의 최소비용
public Vertex(int no, int minDistance) {
this.no = no;
this.minDistance = minDistance;
}
@Override
public int compareTo(Vertex o) {
return this.minDistance - o.minDistance;
}
}
public static void main(String[] args) throws IOException {
BufferedReader bufferedReader = new BufferedReader(new InputStreamReader(System.in));
int v = Integer.parseInt(bufferedReader.readLine());
int[][] adjMatrix = new int[v][v];
int start = 0;
StringTokenizer stringTokenizer = null;
for (int i = 0; i < v; i++) {
stringTokenizer = new StringTokenizer(bufferedReader.readLine());
for (int j = 0; j < v; j++) {
adjMatrix[i][j] = Integer.parseInt(stringTokenizer.nextToken());
}
}
int[] distance = new int[v]; // 출발지에서 자신으로 오는 최소비용
boolean[] visited = new boolean[v]; // 최소비용 확정여부
PriorityQueue<Vertex> priorityQueue = new PriorityQueue<>();
Arrays.fill(distance, Integer.MAX_VALUE);
distance[start] = 0; // 시작점 0으로
priorityQueue.offer(new Vertex(start, distance[start]));
for (int i = 0; i < v; i++) {
// step 01. 최소비용이 확정되지 않은 정점 중 최소비용의 정점 선택
Vertex current = priorityQueue.poll();
if (visited[current.no]) {
continue;
}
visited[current.no] = true;
// step 02. 선택된 정점을 경유지로 하여 아직 최소비용이 확정되지 않은 다른 정점의 최소비용을 고려
for (int j = 0; j < v; j++) {
if (!visited[j] && adjMatrix[current.no][j] != 0 && distance[j] > distance[current.no]+adjMatrix[current.no][j]) {
distance[j] = distance[current.no] + adjMatrix[current.no][j];
priorityQueue.offer(new Vertex(j, distance[j]));
}
}
}
System.out.println(Arrays.toString(distance));
}
}public class DijkstraWithPQ {
static class Vertex implements Comparable<Vertex> {
int no; // 정점 번호
int minDistance; // 출발지에서 자신으로의 최소비용
public Vertex(int no, int minDistance) {
this.no = no;
this.minDistance = minDistance;
}
@Override
public int compareTo(Vertex o) {
return this.minDistance - o.minDistance;
}
}
public static void main(String[] args) throws IOException {
BufferedReader bufferedReader = new BufferedReader(new InputStreamReader(System.in));
int v = Integer.parseInt(bufferedReader.readLine());
int[][] adjMatrix = new int[v][v];
int start = 0;
StringTokenizer stringTokenizer = null;
for (int i = 0; i < v; i++) {
stringTokenizer = new StringTokenizer(bufferedReader.readLine());
for (int j = 0; j < v; j++) {
adjMatrix[i][j] = Integer.parseInt(stringTokenizer.nextToken());
}
}
int[] distance = new int[v]; // 출발지에서 자신으로 오는 최소비용
boolean[] visited = new boolean[v]; // 최소비용 확정여부
PriorityQueue<Vertex> priorityQueue = new PriorityQueue<>();
Arrays.fill(distance, Integer.MAX_VALUE);
distance[start] = 0; // 시작점 0으로
priorityQueue.offer(new Vertex(start, distance[start]));
for (int i = 0; i < v; i++) {
// step 01. 최소비용이 확정되지 않은 정점 중 최소비용의 정점 선택
Vertex current = priorityQueue.poll();
if (visited[current.no]) {
continue;
}
visited[current.no] = true;
// step 02. 선택된 정점을 경유지로 하여 아직 최소비용이 확정되지 않은 다른 정점의 최소비용을 고려
for (int j = 0; j < v; j++) {
if (!visited[j] && adjMatrix[current.no][j] != 0 && distance[j] > distance[current.no]+adjMatrix[current.no][j]) {
distance[j] = distance[current.no] + adjMatrix[current.no][j];
priorityQueue.offer(new Vertex(j, distance[j]));
}
}
}
System.out.println(Arrays.toString(distance));
}
}