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

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

다익스트라 알고리즘은 최단경로 알고리즘 중 하나이다. 최단경로 알고리즘의 종류만 짚고 넘어가보자.

최단경로?

간선의 가중치가 있는 그래프에서 두 정점 사이의 경로들 중에 간선의 가중치의 합이 최소인 경로

하나의 시작 정점에서 끝 정점까지의 최단 경로

1. 다익스트라(Dijkstra) 알고리즘  --  음의 가중치를 허용하지 않음.

2. 벨만포드(Bellman-Ford) 알고리즘 -- 음의 가중치 허용

모든 정점들에 대한 최단 경로

1. 플로이드-워샬(Floyd-Warshall) 알고리즘

---

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

• 시작 정점에서 거리가 최소인 정점을 선택해 나가면서 최단 경로를 구하는 방식.

• 시작정점[s]에서 끝정점[t]까지의 최단경로에 정점 x가 존재한다.

• 이때, 최단경로는 s에서 x까지의 최단경로와 x에서 t까지의 최단경로로 구성된다.

• 탐욕(greedy) 기법을 사용한 알고리즘으로 MST의 프림(Prim)알고리즘과 유사하다.

아래 구조를 따라 구현해보면 다익스트라 구현이 가능하다.

 

1. 출발 노드를 지정
2. 출발 노드를 기준으로, 각 노드의 최소 비용을 저장
3. 방문하지 않은 노드 중에서 가장 비용이 적은 노드를 선택.
4. 해당 노드를 거쳐서 특정한 노드로 가는 경우를 고려하여 최소 비용을 갱신
5. 위 과정에서 3~4번의 과정을 반복.

 

 

 
public class Dijkstra {
    static final int N = 6;
    static int M = Integer.MAX_VALUE;
    static int[][] adj = {
            {0,3,5,M,M,M,}
            ,{M,0,2,6,M,M}
            ,{M,1,0,4,6,M}
            ,{M,M,M,0,2,3}
            ,{3,M,M,M,0,6}
            ,{M,M,M,M,M,0}
    };
    
    static boolean[] visited = new boolean[N];
    static int[] dist = new int[N];
    
    public static void main(String[] args) {
        
        dijkstra(0);
        for(int i=0; i<N; i++) {
            System.out.println(dist[i]);
        }
    }
    
    //가장 최소 거리를 가지는 정점을 반환
    static int getSmallIndex() {
        int min = Integer.MAX_VALUE;
        int idx = -1;
        for(int i=0; i<N; i++) {
            if( !visited[i] && dist[i] < min) {
                min = dist[i];
                idx = i;
            }
        }
        return idx;
    }//end getSmallIndex method
    
    static void dijkstra(int start) {
        for(int i=0; i<N; i++) {
            //시작점에서 출발했을 때,모든 경로의 cost
            dist[i] = adj[start][i];
        }
        
        //시작점 방문처리 
        visited[start] = true;
        
        for(int i=0; i<N-2; i++) {
            //현재 방문하지 않은 node 중에서, 빠르게 도착할 수 있는
            //즉 최소 cost를 가지는 index를 가져옴.
            int curr = getSmallIndex();
            //가져온 index를 방문처리 
            visited[curr] = true;
            
            //위 노드와 인접한 노드들을 모두 확인 
            for(int j=0; j<N; j++) {
                // 인접 노드 중, 방문하지 않은 곳이 있다면 
                if(!visited[j] && adj[curr][j] != M && dist[j]> dist[curr]+adj[curr][j]) {
                        dist[j] = dist[curr] + adj[curr][j];
                }
            }
        }
    }
}
 

result : 0 3 5 9 11 12