[알고리즘] 다익스트라 최단 경로 알고리즘 (Dijkstra Algorithm)

---

[알고리즘] 다익스트라 최단 경로 알고리즘 (Dijkstra Algorithm)

---

다익스트라 알고리즘은 출발지 -> 경유지 -> 목적지를 이용하여 최단 경로를 구하게 된다.

이 과정을 반복하게 되면 고정된 출발지에서 모든 edge의 최단 경로를 구할 수 있다.

 

 

필요 사항

우선 순위 큐 (순서대로 확인하는 것이 아닌, 거리가 가장 짧은 것부터 수행하기 때문에 수행 시간을 단축)

고정된 출발지에서 목적지까지의 경로 값 저장 배열

 

---

 

최소 비용을 만들기 위해 필요한 Node의 개수는 항상 3개라고 생각해야 한다. [출발, 경유, 목적]

 

출발지 -> 경유지, 경유지 -> 목적지로 따로 생각해야 한다.

경유지를 반복문을 돌리므로 목적지는 복수개다.

 

주목할 부분은 경유지 -> 목적지 인 부분이다.

목적지였던 부분이 다음부터 경유지로 사용이 되어

경유지가 향하는 모든 edge의 비용을 확인한다.

 

퍼져나가는 방식으로 최종적으로 모든 노드의 최소 비용을 알 수 있다.

 

round 1 = 경유지 -> 목적지

round 2 = 경유지 -> 목적지 

round 3 = 경유지 -> 목적지

 

[목적지가 최소 경로 비용으로 처리되면 다음부터는 목적지가 경유지로 쓰임]

 

BFS 동작 방식과 유사하다.

 

---

 

동작 예시

 

 

다익스트라 알고리즘은 경유지로 가장 먼저 자기 자신을 기준으로 update 한다.

1번 노드에서 3, 4번 노드를 update 시켜줄 수 있다.

[1 -> 1 -> 3]     [1 -> 1 -> 4]

dist배열 = [INF, 0, INF, 6, 3, INF]  // 0번은 편의를 위해 사용하지 않는다.

 

3, 4번 노드가 update 되고,

큐에 3, 4번 노드가 들어갔다.

 

 

 

 

4번 노드의 가중치가 가장 작으므로 우선순위 큐에 의해 가장 먼저 나온다.

4번 노드에서 2, 3번 노드를 update 시켜줄 수 있다.

[1 -> 4 -> 2]      [1 -> 4 -> 3]

dist배열 = [INF, 0, 4, 4, 3, INF] 

 

2, 3번 노드가 update 되고,

큐에 2, 3번 노드가 들어갔다.

 

현재 큐에 3번 노드가 두 번 들어갔다.

이 경우는 먼저 들어간 3번 노드는 가중치가 6으로 dist [3]의 값보다 크므로 사용되지 않고 버려진다.

1 -> 1 -> 3 경로보다 1 -> 4 -> 3 경로가 최소 비용이므로 1 -> 4 -> 3을 사용하면 되기 때문이다.

(update 된 거리보다 크다면, update 한 노드는 큐에 들어간 것이므로 최소가 보장. 버려도 되는 이유)

 

 

 

이 같은 방식으로 시작 노드를 기준으로 퍼져나가며 모든 노드의 최소 비용을 계산한다.

다익스트라 알고리즘은 방향 그래프여야 하며, 거리가 음수면 안된다.

거리가 음수, 그리고 사이클이 존재한다면 거리를 계속 줄이는 음수 사이클이 발생. -무한대 형성

 

 

---

 

 

public class Dijkstra {
    static int[] dist;
    static int[] path; // 자신의 앞 경로를 갖고 있다. ** 모든 경로를 확인할 수 있다.

    static List<List<Node>> list = new ArrayList<>(); // 간선들

    static final int edgeCount = 5 + 1;
    static final int vCount = 7;

    public static void main(String[] args) {
        //노드 5개
        dist = new int[edgeCount]; // 0 사용안함.
        path = new int[edgeCount];
        //간선 7개
        for(int i = 0; i<=vCount; i++) {
            list.add(new ArrayList<>());
        }

        // (1 - > 5) 2000 쓰는 경로
        list.get(1).add(new Node(4, 2000));
        list.get(1).add(new Node(5, 2000));

        // (1 -> 5) 10 쓰는 경로
        list.get(1).add(new Node(2, 5));
        list.get(2).add(new Node(5, 5));

        // (1 -> 5) 3 쓰는 경로
        list.get(1).add(new Node(3, 1));
        list.get(3).add(new Node(4, 1));
        list.get(4).add(new Node(5, 1));

        
        // TODO: 이 부분 주의 자신은 0으로 만들어야함
        // 자기 자신 빼고 나머지 INF 로 초기화
        Arrays.fill(dist, 100_000_000);
        dist[1] = 0; // 시작

        
        dijk();

        // 결과
        System.out.println(Arrays.toString(dist));
        // 경로
        System.out.println(Arrays.toString(path));
    }

    // TODO: 출발지 1번은 계속 고정
    public static void dijk(){
        Queue<Node> q = new PriorityQueue<>((o1,o2) -> o1.w - o2.w);
        q.add(new Node(1, 0)); // 경유지, 비용 (1 -> 1 -> n)

        while(!q.isEmpty()) { // TODO: 경유지 뽑기 // 1 -> M
            Node mid = q.poll(); // 1과 연결된 경유지
            
            // 과거 ,  현재
            if(mid.w > dist[mid.dest]) // update 된 거리보다 큐에서 뽑은게 더 크면 사용 안하고 버림
                continue;

            // TODO: 경유 -> 도착 꺼내는 부분
            for(Node d : list.get(mid.dest)){
                if(dist[d.dest] > dist[mid.dest] + d.w){ // 갱신이 되는 부분.
                    dist[d.dest] = dist[mid.dest] + d.w;
                    // 갱신이 된 것. 1->n , n->M
                    // (1 -> 도착지)  [[ (1 -> 경유(테이블)  + 경유(테이블) - > 도착지 ]]
                    // 계속 갱신       계속 생신

                    // TODO: 현재 목적지가 다음부터는 경유지로 쓰인다.
                    q.offer(new Node(d.dest, dist[d.dest]));
                    // 갱신된 (1 -> 목적지) 를 넣어준다.
                    // 갱신된걸 넣지 않으면 for 부분을 또 확인하기 때문에 갱신된 값을 넣어주는게 좋다.

                    path[d.dest] = mid.dest; // 길찾기 용도 (자신의 앞 노드)
                }
            }
        }
    }
}

// 경유지로도 쓰고, 목적지로도 쓰임
class Node{
    int dest; // 도착지
    int w; // 가중치

    Node(int dest, int w){
        this.dest = dest;
        this.w = w;
    }

    public String toString(){
        return this.dest + " " + this.w;
    }
}

 

 

 

 

 

 

 

 

 

 

---