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

- 다이나믹 프로그래밍을 활용한 최단경로 탐색 알고리즘

- 인공위성 GPS 소프트웨어 등에서 많이 사용이 됨

- 특정한 하나의 정점에서 다른 모든 정점으로 가는 최단 경로를 찾아줌

- 무방향, 유방향 그래프 두 종류 다 작동을 함

 

*문제상황

4번 노드에서 6번 노드로 가는 최단 경로를 찾아보자

 

- 출발 노드를 시작으로 노드를 하나씩 조사를 해 나아가는데 그 기준은 1) 조사를 아직 하지 않은 노드 중에서 2) 가장 최단거리로 갈 수 있는 노드를 조사하게 된다.

- 우선순위 큐를 이용하여 조사하는 노드들 중에서(조사하지 않은 노드 중) 현재 가장 최단거리로 갈 수 있는 노드를 조사

 

Step1 출발점에서 해당 노드까지 갈 수 있는 최단 경로의 가중치를 저장하는 일차원 배열을 생성한다. (result배열)

- 처음에는 무한대 값으로 모든 배열 부분에 저장(아주 큰 수)

 

Step2 출발 노드를 우선순위 큐에 저장 한 다음 각 노드에 대하여  갈 수 있는 최단 거리를 저장

 

Step3 조사를 하는 노드를 기준으로 이어져 있는 노드를 대상으로 현재 판단된 최단거리(result배열)보다 짧은 거리가 발견되면 우선순위 큐에 넣고  조사를 진행

 

Step4 우선순위 큐가 비어있을 때 까지 반복

 

이를 그림으로 나타내어 보면 다음과 같다.

 

- 4번 노드 조사

 

- 1번노드 조사

 

- 2번노드 조사

- 3번노드 조사

- 5번,6번노드는 위와 같은 방식으로 동일하게 조사

 

소스코드

import java.util.ArrayList;
import java.util.List;
import java.util.PriorityQueue;

public class DijstraAlgorithm {

    static final int INF = 10000000;

    static int[] result = new int[7];

    static class MapInfo{
        int node;
        int weight;

        public MapInfo(int node, int weight){
            this.node = node;
            this.weight = weight;
        }

    }

    static class Search implements Comparable<Search>{
        int adjacentNode;
        int weight;

        public Search(int adjacentNode,int weight){
            this.adjacentNode = adjacentNode;
            this.weight  =weight;
        }

        @Override
        public int compareTo(Search search) {
            return this.weight - search.weight;
        }
    }

    static void dijstra(int start, List<List<MapInfo>> map){
        result[start] = 0;
        PriorityQueue<Search> pq = new PriorityQueue<>();
        pq.add(new Search(4,0));

        while(!pq.isEmpty()){
            int searchNode = pq.peek().adjacentNode;
            int accumulateDist = pq.peek().weight;
            pq.poll();
            for(int i = 0 ; i < map.get(searchNode).size(); i++){
                int adjacentNode  = map.get(searchNode).get(i).node;
                int adjacentDist = accumulateDist + map.get(searchNode).get(i).weight;

                if(adjacentDist < result[adjacentNode]){
                    result[adjacentNode] = adjacentDist;
                    pq.add(new Search(adjacentNode,adjacentDist));
                }

            }

        }
    }

    public static void main(String[] args) {
        for(int i = 0 ; i < 7; i++){
            result[i] = INF;
        }

        //노드 연결정보 저장
        List<List<MapInfo>> map = new ArrayList<>();
        List<MapInfo> insert = new ArrayList<>();
        map.add(insert);
        insert = new ArrayList<>();

        insert.add(new MapInfo(2,2));
        insert.add(new MapInfo(4,3));
        insert.add(new MapInfo(4,4));
        map.add(insert);
        insert = new ArrayList<>();

        insert.add(new MapInfo(1,2));
        insert.add(new MapInfo(4,4));
        insert.add(new MapInfo(3,2));
        map.add(insert);
        insert = new ArrayList<>();

        insert.add(new MapInfo(2,2));
        insert.add(new MapInfo(5,1));
        insert.add(new MapInfo(6,4));
        map.add(insert);
        insert = new ArrayList<>();

        insert.add(new MapInfo(1,4));
        insert.add(new MapInfo(1,3));
        insert.add(new MapInfo(2,4));
        map.add(insert);
        insert = new ArrayList<>();

        insert.add(new MapInfo(2,6));
        insert.add(new MapInfo(3,1));
        map.add(insert);
        insert = new ArrayList<>();

        insert.add(new MapInfo(3,4));
        map.add(insert);

        dijstra(4,map);

        for(int i =1; i < 7 ; i++){
            System.out.println(i + ": " + result[i]);
        }
    }

}

 

결과

 

* 개인적으로 고민을 했던 부분

- 그래프를 MST로 만든 다음 경로를 탐색하면 이것이 최단경로가 왜 아닐까?

결론은 아니였다!

그 이유는 최단 경로를 탐색하기 위해서는 모든 간선에 대하여 고려를 해야 했고 내가 고민했던 부분의 반례는 다음과 같다.

1번노드에서 3번노드로 가는 최단 경로를 고려 해 볼 경우

노란색 부분은 MST를 생성할 때 생성 될 수 있는 간선이지만(싸이클이 발생되면 안됨으로 푸른색 간선은 포함이 안됨) 최단경로는 푸른색 부분이다.

 

이 글은 해당 블로그를 공부한 바탕으로 만들었습니다.

m.blog.naver.com/ndb796/221234424646

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