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

김준호·2020년 8월 27일

dijkstra 다익스트라 최단경로

알고리즘

목록 보기

7/7

최단경로 알고리즘 시리즈

다익스트라 알고리즘

최단경로를 찾는 알고리즘 중 다익스트라는 오직 양의 가중치를 가진 그래프만을 취급한다. 또한 특정 출발위치에서 도착위치의 최단경로를 찾는 알고리즘으로, 모든 경로의 최단경로를 구하지 않는다.

그리디하게 정점을 선택하여 방문하고, 선택한 정점에서 인접 정점 중 방문되지 않은 것들에 대해 최단 경로를 구해가면서 도착지점에 도달한다.

아래 그래프에서 0번에서 출발해 6번까지 가는 최단경로를 다익스트라로 구해보자.

0번 노드에서 출발해서 방문하지 않은 인접한 노드 중에 가중치가 가장 적은 노드에 대해 방문한다.
현재 그리디하게 선택한 경로의 가중치 합이 나중에 최단 경로가 아닐 수도 있으니 배열에 가중치의 합들을 저장하며 지나간다

1번 노드에서 인접한 노드 중 가중치가 제일 작은것은 4번이다.
이 때, 비교해봐야하는 것은 0번 노드에서 4번노드로 가는 경로 중 현재 선택된 경로보다 가중치가 적은 경로가 있는지 확인해야 한다.
- 현재 0 -> 1 -> 4와 비교를 하기 위해서는 0 -> 3 -> 4의 가중치를 알아야한다.
- 이를 우선순위 큐를 이용해서 누적 가중치가 적은것부터 뽑아내는 것으로 해결한다.

마지막으로 4번노드에서 6번노드로 이동하면 총 가중치가 1 + 1 + 2로 최단경로를 구할 수 있다.
이제 아래 코드에서 어떻게 다른 정점들은 방문하지 않고 최단경로를 찾아냈는지 확인해보자.

구현 🔑

백준 1753 : 최단경로를 다익스트라로 구현해보면서 이해해보자.

        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer st = new StringTokenizer(br.readLine());

        V = Integer.parseInt(st.nextToken());
        E = Integer.parseInt(st.nextToken());
        startNode = Integer.parseInt(br.readLine());

        sb = new StringBuilder();
        dist = new int[V+1];
        adj = new List[V+1];
        for (int i = 0; i < V+1; i++) {
            adj[i] = new ArrayList<>();
        }
        Arrays.fill(dist,Integer.MAX_VALUE);

        for (int i = 0; i < E; i++) {
            st = new StringTokenizer(br.readLine());
            int u = Integer.parseInt(st.nextToken());
            int v = Integer.parseInt(st.nextToken());
            int w = Integer.parseInt(st.nextToken());

            adj[u].add(new int[]{v,w});
        }

우선 입력 받는 부분에서는 유향 그래프라는 점을 주의하고, 앞으로 간선의 가중치를 저장해 놓을 배열을 Integer.MAX_VALUE로 초기화 한다.

    private static void dijkstra() {
        PriorityQueue<int[]> pq = new PriorityQueue<>(new Comparator<int[]>() {
            @Override
            public int compare(int[] o1, int[] o2) {
                if(o1[1] < o2[1]) return -1;
                else return 1;
            }
        });

	... next
    }

다익스트라를 구현하기에 앞서서 우선순위 큐를 가중치가 낮은 정점부터 꺼내는 순으로 구현하자.

    private static void dijkstra() {
	prev ... 

        pq.add(new int[] {startNode,0});
        dist[startNode] = 0;

        while(!pq.isEmpty()) {
            int[] curr = pq.poll();
            int currNode = curr[0];
            int currCost = curr[1];
            if(dist[currNode] != currCost) continue;

            for(int[] next : adj[currNode]) {
                int nextNode = next[0];
                int nextCost = next[1];

                if(dist[nextNode] > dist[currNode] + nextCost) {
                    dist[nextNode] = dist[currNode] + nextCost;
                    pq.offer(new int[] {nextNode,dist[nextNode]});
                }
            }
        }
    }