알고리즘

다익스트라 알고리즘 (Dijkstra Algorithm)

두구둥둥 2021. 4. 4. 00:08

다익스트라 알고리즘 (Dijkstra Algorithm)

다익스트라 알고리즘은 최단경로를 찾는 알고리즘이다.

최단경로 알고리즘 종류

  1. 다익스트라
  2. 벨만포드
  3. 플로이드


음의 가중치가 없을 때, 하나의 정점에서 나머지 모든 정점으로의 최단경로를 구할 때 사용된다.

다익스트라 알고리즘은 DP를 활용한다.
DP가 가능한 이유 > 최단거리는 여러 개의 최단거리로 이루어져 있기 때문!

시간복잡도

V : 정점의 개수, E : 간선 개수

O(V^2)
우선순위큐 사용시 : O((V+E)logN)

O(VlogN) : 미방문 노드 중 현재까지의 최단거리를 가지는 노드 찾기
O(ElogN) : 각 노드마다 이웃한 노드이 최단 거리를 갱신할 때

 

필요 변수

int[] distance // 최단 거리 저장
boolean[] visited // 노드 방문 체크

 

 

 

동작 순서

사전 작업
  1. distance 배열의 값을 모두 무한대로 초기화
  2. graph 만들기
    • 이차원배열
    • 인접리스트
    • 우선순위큐

다익스트라 알고리즘 구현

  1. 시작 노드의 distance값을 0으로 바꾸고, 방문체크하기
  2. 시작 노드와 인접한 노드들의 distance 갱신
  3. 방문하지 않은 노드 중 distance값이 최소인 노드 찾기
  4. 최소 노드 방문 체크
  5. 최소 노드와 인접하면서 아직 방문하지 않은 노드의 distance 갱신
    이때, distance값 보다 distance[최소노드]+최소노드~해당노드 거리가 더 작아야 함.
  6. 모든 노드를 방문할 때까지 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