728x90
그래프에서 꼭짓점 간의 최단 경로를 찾는 알고리즘
가중치가 음수를 가지면 안되고 인접한 정점으로 가는 간선중 가장 적은 비용을 가지는 간선을 택한다. 알고리즘 수행중 새로운 경로가 생기면 그 경로를 기록하고 이후에 생기는 또 다른 경로와 비교하면서 최단 경로를 탐색한다.
다익스트라 알고리즘 순서
1. 최단 거리 값은 무한대 값으로 초기화한다.
for(int i = 1; i <= n; i++){
distance[i] = Integer.MAX_VALUE;
}2. 시작 정점의 최단 거리는 0이다. 그리고 시작 정점을 방문 처리한다.
distance[start] = 0;
visited[start] = true;3. 시작 정점과 연결된 정점들의 최단 거리 값을 갱신한다.
for(int i = 1; i <= n; i++){
if(!visited[i] && map[start][i] != 0) {
distance[i] = map[start][i];
}
}
4. 방문하지 않은 정점 중 최단 거리가 최소인 정점을 찾는다.
int min = Integer.MAX_VALUE;
int midx = -1;
for(int i = 1; i <= n; i++){
if(!visited[i] && distance[i] != Integer.MAX_VALUE) {
if(distance[i] < min) {
min = distance[i];
midx = i;
}
}
}5. 찾은 정점을 방문 체크로 변경 후, 해당 정점과 연결된 방문하지 않은 정점의 최단 거리 값을 갱신한다.
visited[midx] = true;
for(int i = 1; i <= n; i++){
if(!visited[i] && map[midx][i] != 0) {
if(distance[i] > distance[midx] + map[midx][i]) {
distance[i] = distance[midx] + map[midx][i];
}
}
}
6. 모든 정점을 방문할 때까지 4~5번을 반복한다.
다익스트라 인접 행렬로 구현한 코드
public class Dijkstra {
public static void main(String[] args) {
Graph g = new Graph(6); // 노드 수 만큼 그래프 생성
// 시작, 끝, 간선 가중치 입력
g.input(0, 1, 7);
g.input(0, 2, 9);
g.input(0, 5, 14);
g.input(1, 2, 10);
g.input(1, 3, 15);
g.input(2, 3, 11);
g.input(2, 5, 2);
g.input(3, 4, 6);
g.input(4, 5, 9);
// 시작노드 기준 다익스트라 알고리즘 실행
g.dijkstra(0);
}
}
class Graph{
private int n; // 노드들의 수
private int maps[][]; // 노드들간의 가중치 저장할 변수
public Graph(int n){
this.n = n;
maps = new int[n][n];
// 인접행렬 모든 값 무한대로 초기화
for(int i=0; i<n; ++i){
for(int j=0; j<n; ++j){
maps[i][j] = Integer.MAX_VALUE;
}
}
}
public void input(int i,int j,int w){
maps[i][j] = w;
maps[j][i] = w;
}
public void dijkstra(int v){
int distance[] = new int[n]; // 최단 거리를 저장할 변수
boolean[] check = new boolean[n]; // 해당 노드를 방문했는지 체크할 변수
// distance값 초기화. 무한대를 int 자료형의 최대값으로 표현했다.
for(int i=0; i<n; ++i){
distance[i] = Integer.MAX_VALUE;
}
// 시작노드값 초기화.
distance[v] = 0;
check[v] = true;
// 결과값 출력
for(int i=0; i<n; ++i){
if(distance[i] == 2147483647) System.out.print("∞ ");
else System.out.print(distance[i]+" ");
}
System.out.println("");
// 연결노드 distance갱신
for(int i=0; i<n; ++i){
if(!check[i] && maps[v][i] != Integer.MAX_VALUE){
distance[i] = maps[v][i];
}
}
// 결과값 출력
for(int i=0; i<n; ++i){
if(distance[i] == 2147483647) System.out.print("∞ ");
else System.out.print(distance[i]+" ");
}
System.out.println("");
for(int a=0; a<n-1; ++a){
// 원래는 모든 노드가 true될때까지 인데
// 노드가 n개 있을 때 다익스트라를 위해서 반복수는 n-1번이면 된다.
// 원하지 않으면 각각의 노드가 모두 true인지 확인하는 식으로 구현해도 된다.
int min = Integer.MAX_VALUE;
int min_index = -1;
// 노드 최소값 찾기
for(int i=0; i<n; ++i){
if(!check[i]){
if(distance[i] < min){
min = distance[i];
min_index = i;
}
}
}
// 다른 노드를 거쳐서 가는 것이 더 비용이 적은지 확인한다.
check[min_index] = true;
for(int i=0; i<n; ++i){
if(!check[i] && maps[min_index][i] != Integer.MAX_VALUE){
if(distance[min_index] + maps[min_index][i] < distance[i]){
distance[i] = distance[min_index] + maps[min_index][i];
}
}
}
// 결과값 출력
for(int i=0; i<n; ++i){
if(distance[i] == 2147483647) System.out.print("∞ ");
else System.out.print(distance[i]+" ");
}
System.out.println("");
}
}
다익스트라 적용 시 알아아할 점
- 인접 행렬로 구현 시 시간 복잡도는 O(n²)이다.
- 인접 리스트로 구현 시 시간 복잡도는 O(nlogn)이다.
- 선형 탐색으로 시간 초과가 날 시 인접 리스트로 접근해야한다(우선순위 큐)
- 간선의 값이 양수일 때만 가능하다.
실생활 응용
- 가능한 적은 비용으로 가장 빠르게 해답에 도달하는 경로를 찾아내는 대부분 문제에 해당된다.
- 내비게이션, 미로탐색 알고리즘, 최소 운송비 지점 구하기, 가장 빠른 길 찾기 등에 이용된다.
출처: