다익스트라(Dijkstra Algorithm)

하나의 정점에서 다른 모든 정점들의 경로를 구하는 알고리즘이다.

간선들은 모두 양의 간선들을 가져야 한다.

Dijkstra의 알고리즘에서는 시작 정점에서 집합S에 있는 정점만을 겨처서 다른 정점으로 가는 최단 거리를 기록하는 배열이 있어야 하는데 이 배열을 우선순위 큐로 구현하여 해당 큐에 들어간 Node중에 가중치가 젤 작은 정점을 가져오도록 구현해야 한다.

 

시작 정점을 0으로 잡고, 각 지점까지의 거리를 표시한다. 여기서 각 정점까지의 정보와 거리를 우선순위 큐에 넣는다.

그리고 우선순위 큐에서 가장 짧은 거리인 4정점까지의 거리인 3이므로 4정점에서 시작을 한다. 나는 해당 배열을 우선순위 큐로 구현하였다.

 

우선수위 큐 구현(가장 작은 값 순서로)

package org.kyhslam.cps.section4;

import java.util.ArrayList;
import java.util.PriorityQueue;
import java.util.Scanner;

// 다익스트라 알고리즘(우선순위 큐)
public class cp80 {

    static ArrayList<Edge>[] a;
    static boolean[] visited;
    static int[] distance;

    public static class Edge implements Comparable<Edge> {

        int y;
        int dis;

        public Edge(int y, int dis) {
            this.y = y;
            this.dis = dis;
        }

        @Override
        public int compareTo(Edge o) {
            return this.dis <= o.dis ? -1 : 1;
        }
    }


    public static void main(String[] args) {

        Scanner sc = new Scanner(System.in);

        int N = sc.nextInt();
        int M = sc.nextInt();

        a = (ArrayList<Edge>[]) new ArrayList[N+1];
        visited = new boolean[N+1];
        distance = new int[N+1];

        for(int i=1; i <= N; i++){
            a[i] = new ArrayList<Edge>();
            distance[i] = 21470000;
        }

        for(int i=1; i <= M; i++){
            int x = sc.nextInt();
            int y = sc.nextInt();
            int dis = sc.nextInt(); // 거리

            a[x].add(new Edge(y,dis));
        }

        //우선순위 큐
        PriorityQueue<Edge> priorityQueue = new PriorityQueue<>();


        // 1부터 시작
        priorityQueue.add(new Edge(1,0));

        //탐색 시작
        while( !priorityQueue.isEmpty() ){

            Edge eg = priorityQueue.poll(); // 빼기
            int now = eg.y;
            int cost = eg.dis;

            visited[now] = true;

            for(int i=0; i < a[now].size(); i++){
                Edge node = a[now].get(i);
                int next = node.y;
                int nextDis = node.dis + cost;

                // 해당 정점에 연결된 정점 중에 탐색안해도 되는건 제외한다
                if(visited[next] == false){

                    // distance 거리보다 작은 값을 경우에 우선순위 큐에 넣어 준다.
                    if(nextDis < distance[next]){
                        distance[next] = nextDis;
                        priorityQueue.add(new Edge(next,nextDis));
                    }
                }
            }

        }






        for(int i=1; i < a.length; i++){
            for(int y=0; y < a[i].size(); y++){
                Edge ee =   a[i].get(y);
                //System.out.println(i + " === " +  ee.y + " : " + ee.dis);
            }
        }


        for(int i=1; i <= N; i++){
            System.out.println(i + " == " + distance[i]);
        }

    }
}