다익스트라 알고리즘
- 한 정점에서 다른 모든 정점까지의 최단 경로를 구하는 알고리즘
- 겨올탐색, 네트워크 라우팅 등 분야에서 활용될 수 있음
- 그리디 기법
동작 원리
1. 출발 정점에서 시작. 인접 정점 중 가장 짧은 경로를 갖는 정점을 선택
2. 선택 정점에서 다른 인접 정점까지의 거리를 계산하고, 이전에 계산된 거리와 비교해 더 짧은 경로가 발견되면 해당 경로로 업데이트.
3. 같은 방법으로 최단 경로를 찾을 때까지 진행
장점
- 탐색속도: 모든 간선이 음수가 아닐 때 빠른 탐색 속도로 경로 탐색 가능
- 우선순위 큐를 활용해 시간 복잡도 절감 가능
단점
- 음수 가중치가 있는 그래프에서는 작동 X
- 배열을 활용한 방법의 경우 간선이 많을수록 성능 저하될 수 있음
구현
1.방문체크배열(visited), 인접배열(adjArr), 시작점으로부터의 거리(dist)를 저장할 배열이 필요
2. dist배열을 모두 무한대로 설정하고, 탐색 시작할 정점만 0으로 변경
3. 현재 방문하지 않은 정점 중 가장 짧은 거리를 가진 정점을 선택
4. 인접배열을 통해 탐색하고자 하는 정점과 인접한 정점들의 거리를 더 짧은 거리로 업데이트
<배열을 활용한 방법>
import java.util.Arrays;
public class DijkstraArray {
// 정점의 개수 V, 무한대 값으로 사용할 상수
static final int V = 5;
static final int INF = Integer.MAX_VALUE;
// 다익스트라 알고리즘을 배열 기반으로 구현
public static void dijkstra(int[][] adjMatrix, int start) {
// 각 정점까지의 최소 거리를 저장하는 배열
int[] dist = new int[V];
// 방문 여부를 저장하는 배열
boolean[] visited = new boolean[V];
// 초기화: 모든 거리를 무한대로 설정하고, 시작 정점의 거리를 0으로 설정
Arrays.fill(dist, INF);
dist[start] = 0;
// 모든 정점을 하나씩 처리
for (int i = 0; i < V - 1; i++) {
// 방문하지 않은 정점 중 가장 거리가 짧은 정점을 선택
int u = selectMinVertex(dist, visited);
// 선택된 정점을 방문 처리
visited[u] = true;
// 인접한 정점들의 거리를 업데이트
for (int v = 0; v < V; v++) {
if (!visited[v] && adjMatrix[u][v] != 0 && dist[u] != INF && dist[u] + adjMatrix[u][v] < dist[v]) {
dist[v] = dist[u] + adjMatrix[u][v];
}
}
}
// 최종 최단 경로 출력
printSolution(dist);
}
// 방문하지 않은 정점 중 최소 거리를 가진 정점을 선택
public static int selectMinVertex(int[] dist, boolean[] visited) {
int min = INF, minIndex = -1;
for (int v = 0; v < V; v++) {
if (!visited[v] && dist[v] < min) {
min = dist[v];
minIndex = v;
}
}
return minIndex;
}
// 최단 경로를 출력하는 메서드
public static void printSolution(int[] dist) {
System.out.println("정점별 최단 거리:");
for (int i = 0; i < V; i++) {
System.out.println(i + " -> " + dist[i]);
}
}
public static void main(String[] args) {
// 그래프의 인접 행렬 표현
int[][] adjMatrix = {
{ 0, 10, 0, 30, 100 },
{ 10, 0, 50, 0, 0 },
{ 0, 50, 0, 20, 10 },
{ 30, 0, 20, 0, 60 },
{ 100, 0, 10, 60, 0 }
};
// 다익스트라 알고리즘 실행 (시작 정점: 0)
dijkstra(adjMatrix, 0);
}
}
<우선순위큐를 활용한 방법>
import java.util.*;
public class DijkstraPriorityQueue {
static final int V = 5;
static final int INF = Integer.MAX_VALUE;
// 간선 클래스 (정점과 가중치)
static class Edge implements Comparable<Edge> {
int vertex, weight;
Edge(int vertex, int weight) {
this.vertex = vertex;
this.weight = weight;
}
// 가중치 기준으로 우선순위 큐에서 정렬
public int compareTo(Edge other) {
return this.weight - other.weight;
}
}
// 다익스트라 알고리즘을 우선순위 큐로 구현
public static void dijkstra(int[][] adjMatrix, int start) {
// 최소 거리를 저장하는 배열
int[] dist = new int[V];
// 우선순위 큐
PriorityQueue<Edge> pq = new PriorityQueue<>();
// 초기화: 모든 거리를 무한대로 설정하고, 시작 정점의 거리를 0으로 설정
Arrays.fill(dist, INF);
dist[start] = 0;
// 시작 정점을 우선순위 큐에 삽입
pq.add(new Edge(start, 0));
// 우선순위 큐가 빌 때까지 반복
while (!pq.isEmpty()) {
Edge current = pq.poll(); // 현재 정점
int u = current.vertex;
// 인접한 정점들의 거리 업데이트
for (int v = 0; v < V; v++) {
if (adjMatrix[u][v] != 0 && dist[u] != INF && dist[u] + adjMatrix[u][v] < dist[v]) {
dist[v] = dist[u] + adjMatrix[u][v];
pq.add(new Edge(v, dist[v]));
}
}
}
// 최종 최단 경로 출력
printSolution(dist);
}
// 최단 경로를 출력하는 메서드
public static void printSolution(int[] dist) {
System.out.println("정점별 최단 거리:");
for (int i = 0; i < V; i++) {
System.out.println(i + " -> " + dist[i]);
}
}
public static void main(String[] args) {
// 그래프의 인접 행렬 표현
int[][] adjMatrix = {
{ 0, 10, 0, 30, 100 },
{ 10, 0, 50, 0, 0 },
{ 0, 50, 0, 20, 10 },
{ 30, 0, 20, 0, 60 },
{ 100, 0, 10, 60, 0 }
};
// 다익
