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

최단 경로를 구하는 알고리즘 중 하나이다. 지난번 cs 네트워크 라우터 관련 검색하다가 잠깐 살펴본 내용인데 이번 기회에 흐름을 익혀보고자 글을 작성한다.

위의 그래프 에서 각 노드 간 의 최단거리를 구하는 방법 중 하나이다. 

distance 의 배열이 존재하고 모두 최대 값 혹은 엄청 큰수로 초기화를 진행한다. 배열 의 수는 노드의 갯수 만큼 구성해서 계속 저장해 가며 값을 기록한다.

0번 에서 출발한다고 할시 갈수 있는경우 0-1, 0-2 이 가존재하며 배열에는 아래와 같이 기록한다.

distance =  0 | 5 | 1 | INF | INF | INF  => 최초 시작점을 0 으로 대입해 시작 하며 이후 다음 노드는 거리가 가장 짧은 2번 부터 진행한다. 이렇게 진행하며 현재 진행 중인 간선의 수가 노드의 갯수-1 이된다면 진행을 멈추고 마지막 값을 리턴하면 그것 이 최단 거리가 된다.

코드로 구현해보자.

class Node{
    int to;
    int distnace;

    public Node(int to, int distance) {
        this.to = to;
        this.distnace = distance;
    }
}

각각 의 노드 에 대한 정보를 기록하기 위해 이너클래스 로 노드를 하나 구성해준다.

class Dijkstra{
	public void dijkstra(int[][] locateInfo, int edge, int start){
        ArrayList<ArrayList<Node>> graph = new ArrayList();
        for(int i=0;i<edge;i++){
            graph.add(new ArrayList());
        }
        for(int i=0;i< locateInfo.length;i++){
            int from = locateInfo[i][0];
            int to = locateInfo[i][1];
            int distance = locateInfo[i][2];
            graph.get(from).add(new Node(to,distance));
        }
    }
}

노드 를 담기 위한 2중 리스트를 생성 해준다. 각 첫번째 리스트 는 현재 엣지 를 의미하고 그안에 담긴 리스트 들은 갈수 있는 경로 를 생성해 더해준다.

public void dijkstra(int[][] locateInfo, int edge, int start){
        ArrayList<ArrayList<Node>> graph = new ArrayList();
        for(int i=0;i<edge;i++){
            graph.add(new ArrayList());
        }
        for(int i=0;i< locateInfo.length;i++){
            int from = locateInfo[i][0];
            int to = locateInfo[i][1];
            int distance = locateInfo[i][2];
            graph.get(from).add(new Node(to,distance));
        }

        int[] shortest_dist = new int[edge];
        Arrays.fill(shortest_dist,1,shortest_dist.length,1<<30);
        PriorityQueue<Node> q = new PriorityQueue<>((x,y)->x.distnace - y.distnace);
        boolean[] visit = new boolean[edge+1];
        q.offer(new Node(start,0));
    }

거리 들을 기록할 배열을 하나 생성해주고 , 2^31-1 이 int 의 최대값이니 그전 까지 업데이트 해주자 전에 한번 overflow 나고 나서부터는 이렇게 초기화를 진행하고 있다.

우선순위 큐를 거리가 짧은 순으로 해서 생성해주고, 마지막까지 가는데 있어 중복 계산을 피할 방문 배열을 생성해준다.

처음 시작점을 변수로 제공받기 떄문에 큐안에 시작점을 넣어주자

public void dijkstra(int[][] locateInfo, int edge, int start){
        ArrayList<ArrayList<Node>> graph = new ArrayList();
        for(int i=0;i<edge;i++){
            graph.add(new ArrayList());
        }
        for(int i=0;i< locateInfo.length;i++){
            int from = locateInfo[i][0];
            int to = locateInfo[i][1];
            int distance = locateInfo[i][2];
            graph.get(from).add(new Node(to,distance));
        }

        int[] shortest_dist = new int[edge];
        Arrays.fill(shortest_dist,1,shortest_dist.length,1<<30);
        PriorityQueue<Node> q = new PriorityQueue<>((x,y)->x.distnace - y.distnace);
        boolean[] visit = new boolean[edge+1];
        q.offer(new Node(start,0));

        while(!q.isEmpty()){
            Node cur = q.poll();
            if(visit[cur.to]) continue;
            visit[cur.to] = true;
            for (int i = 0; i < graph.get(cur.to).size(); i++) {
                Node next = graph.get(cur.to).get(i);
                if(visit[next.to]) continue;
                if(shortest_dist[next.to] > cur.distnace+next.distnace){
                    shortest_dist[next.to] = cur.distnace+next.distnace;
                    q.offer(new Node(next.to,shortest_dist[next.to]));
                }
            }
        }
        System.out.println(Arrays.toString(shortest_dist));
    }

큐 안이 비어있기 전까지 계속 반복문 을 돌려준다. 대신 모든 곳을 방문 했다면 큐 를 계속해서 뽑아오기 때문에 반복문 아래부분 까지 내려가지 않고 계속 뽑아주어 함수를 종료해준다.

 

현재 가려는 방향의 엣지를 받아와 그안에 들어있는 갈수있는 방향들에 대한 정보들을 뽑아와 기록 되어있는 거리와 현재 거리+다음 노드의 거리 를 이용해 최소값을 계속 업데이트 하는 방식이다. 만약 그렇게 업데이트 가 되었다면 큐에 다시 넣어주어 새로운 지점에서 시작하는 노드를 넣어준다. 2~3 번 이상 계속 노트에 손코딩 하다보니 외워버렸지만 미래에 찾고있을 나를 위해 이렇게 정리해 보았다.