다익스트라(Dijkstra) - 최단경로 찾기

□ 예제 : https://www.acmicpc.net/problem/1916

□ 사용처 : 가중치가 있는 그래프에서 최단 경로를 찾는 알고리즘으로, 음수 가중치가 없는 경우에만 사용

 

□ 구현

1. 변수선언

    static int N;
    static int M;
    static List<Node>[] bus;
    static int[] cost;
    static boolean[] check;

• N : 종점 수
• M : 노선 수
• List<Node>[] bus : 버스 노선 인접리스트
• cost : 비용 배열

2. Node 클래스 선언

    static class Node {
        int destination;
        int cost;

        public Node(int e, int cost) {
            this.destination = e;
            this.cost = cost;
        }
    }

 

3. 입력받기

static void input() throws IOException {
        N = Integer.parseInt(br.readLine());
        M = Integer.parseInt(br.readLine());
        bus = new ArrayList[N + 1];
        cost = new int[N + 1];

        for (int i = 0; i < N + 1; i++) {
            bus[i] = new ArrayList<>();
        }


        for (int i = 0; i < M; i++) {
            st = new StringTokenizer(br.readLine());
            int start = Integer.parseInt(st.nextToken());
            int destination = Integer.parseInt(st.nextToken());
            int cost = Integer.parseInt(st.nextToken());

            bus[start].add(new Node(destination, cost));
        }
    }

 

 

4. Dijkstart 알고리즘

static int Dijkstra(int s, int e){
        PriorityQueue<Node> pq = new PriorityQueue<>((o1, o2) -> o1.cost - o2.cost);
        Arrays.fill(cost, Integer.MAX_VALUE);
        cost[s] = 0;
        pq.add(new Node(s, 0));

        while (!pq.isEmpty()) {
            Node now = pq.poll();
            int nowDest = now.destination;
            int nowCost = now.cost;

            if(cost[nowDest] < nowCost) continue;

            for (Node nextBus : bus[nowDest]) {
                int nextDest = nextBus.destination;
                int nextCost = nextBus.cost;

                if (cost[nowDest] + nextCost < cost[nextDest]) {
                    cost[nextDest] = cost[nowDest] + nextCost;
                    pq.add(new Node(nextDest, cost[nextDest]));
                }
            }
        }

        return cost[e];
    }

• (o1, o2) -> o1.cost - o2.cost : 람다식을 통해 우선순위 큐 오름차순 정렬
• cost배열을 최대값으로 채우기
• 시작점 cost를 0으로 초기화
• 시작점 Node를 우선순위 큐에 추가
• 큐에서 Node를 꺼낸 후 지금 cost가 다음 Node의 cost값보다 작으면 continue
• 인접리스트를 순회하며 다음 Node에 대해서 현재목적지 cost값 + 다음 cost가 다음 목적지 cost보다 작으면 작은값으로 갱신하고 큐에 추가
• 큐가 빌때까지 반복