다익스트라 알고리즘 (Dijkstra Algorithm)
다익스트라 알고리즘은 최단경로를 찾는 알고리즘이다.
최단경로 알고리즘 종류
- 다익스트라
- 벨만포드
- 플로이드

음의 가중치가 없을 때, 하나의 정점에서 나머지 모든 정점으로의 최단경로를 구할 때 사용된다.
다익스트라 알고리즘은 DP를 활용한다.
DP가 가능한 이유 > 최단거리는 여러 개의 최단거리로 이루어져 있기 때문!
시간복잡도
V : 정점의 개수, E : 간선 개수
O(V^2)
우선순위큐 사용시 : O((V+E)logN)
O(VlogN) : 미방문 노드 중 현재까지의 최단거리를 가지는 노드 찾기
O(ElogN) : 각 노드마다 이웃한 노드이 최단 거리를 갱신할 때
필요 변수
int[] distance // 최단 거리 저장
boolean[] visited // 노드 방문 체크
동작 순서
사전 작업
- distance 배열의 값을 모두 무한대로 초기화
- graph 만들기
- 이차원배열
- 인접리스트
- 우선순위큐
다익스트라 알고리즘 구현
- 시작 노드의 distance값을 0으로 바꾸고, 방문체크하기
- 시작 노드와 인접한 노드들의 distance 갱신
- 방문하지 않은 노드 중 distance값이 최소인 노드 찾기
- 최소 노드 방문 체크
- 최소 노드와 인접하면서 아직 방문하지 않은 노드의 distance 갱신
이때, distance값 보다 distance[최소노드]+최소노드~해당노드 거리가 더 작아야 함. - 모든 노드를 방문할 때까지 3-5 반복
구현 코드
위의 이미지를 구현..
이차원 배열 그래프로 구현
import java.util.Arrays;
public class Dijkstra2 {
public static void main(String[] args) {
int N = 8;
int[][] input = {{1,2,3},{1,5,4},{1,4,4},{2,3,2},{3,4,1},{4,5,2},{5,6,4},{4,7,6},{7,6,3},{3,8,3},{6,8,2}};
int[] answer = dijkstra(N,input);
System.out.println(Arrays.toString(answer));
}
private static int[] dijkstra(int N,int[][] input){
int[] distance = new int[N+1]; //1에서 출발해서 갈 수 있는 최단거리 배열
for (int i = 1; i < distance.length; i++) {
distance[i] = Integer.MAX_VALUE;
}
boolean[] visited = new boolean[N+1];
int[][] map = new int[N+1][N+1];
for (int i = 0; i < input.length; i++) {
map[input[i][0]][input[i][1]] = input[i][2];
map[input[i][1]][input[i][0]] = input[i][2];
}
//1이 시작점!
distance[1] = 0;
visited[1] = true;
for (int i = 2; i <= N; i++) {
if(map[1][i]!=0) distance[i] = map[1][i];
}
//n-1번 노방문 체크
for (int i = 0; i < N-1; i++) {
int min = Integer.MAX_VALUE;
int minIdx = 0;
//distance중 방문하지 않은 곳들 중 거리 최소 찾기
for (int j = 2; j <= N; j++) {
if(visited[j]) continue;
if(min>distance[j]) {
min = distance[j];
minIdx = j;
}
}
//minIdx를 방문하고 거기서 또 최소값 갱신
visited[minIdx] = true;
for (int j = 2; j <= N; j++) {
if(visited[j] || map[minIdx][j] == 0) continue;
if(map[minIdx][j]+distance[minIdx] < distance[j]) distance[j] = map[minIdx][j]+distance[minIdx];
}
}
return distance;
}
}
'알고리즘' 카테고리의 다른 글
MST : 최단경로 알고리즘 (크루스칼/프림) (0) | 2021.05.30 |
---|---|
Binary Search(이진탐색/이분탐색) (0) | 2021.04.25 |
최단경로 알고리즘 (0) | 2021.04.04 |