[Java] 다익스트라 알고리즘(Dijkstra Algorithm) + 예제

다익스트라 알고리즘

V = vertext(정점) , E = edge(간선) , adjNode = adjacentNode(인접노드)

 

- 최단경로를 구하는 알고리즘

- 하나의 정점을 기준으로 다른 정점까지 가는 최단거리를 구한다. (출발지에서 다른 정점까지의 최단거리들을 구한다)

- 음수 가중치가 없어야한다

- 인접 행렬로 표현된 그래프로 다익스트라 알고리즘을 구현시 시간 복잡도 O(V^2)

- 우선순위 큐+리스트를 사용해서 다익스트라 알고리즘 구현시 시간복잡도 ( ElogV) 까지 낮출수 있다고 한다.

- 탐욕법(그리디 알고리즘) 과 동적 계획법(다이나믹 프로그래밍)을 사용한다.

   -> 방문하지 않은 노드 중에서 가장 비용이 적은 노드를 선택한다 (그리디 알고리즘)

   -> 해당 노드로부터 갈 수 있는 노드들의 비용을 보고, 출발지 -> 다른노드 의 최소 비용값들을 갱신한다( 다이나믹 프로         그래밍)

다익스트라 알고리즘 과정

(방문배열을 사용하는 방법)

[알고리즘/Java]다익스트라(Dijkstra) 알고리즘

(인접행렬을 이용한 방법, 방문배열을 사용하지않는 방법)

[Java]다익스트라 알고리즘(Dijkstra Algorithm)

 

간선의 가중치가 같다면 bfs,dfs를 사용하지만

 

다를때는 다익스트라를 사용한다.

 

(음수 가중치가 있다면 다익스트라를 사용할 수 없다.)

 

코드

방문배열을 이용한 코드. (참고)

public class Main {

    static BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
    static BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));


    /*
     */

    static boolean[] visited;
    static int v,e,start;
    static List<List<Node>> graph = new ArrayList<>();
    static int[] distance;


    public static void main(String[] args) throws IOException {
        input();
        solve();

        bw.flush();
        bw.close();

    }

    static void input() throws IOException {
        int[] input = Arrays.stream(br.readLine().split(" ")).mapToInt(Integer::parseInt).toArray();
        v = input[0]; //정점
        e = input[1]; //간선
        start = Integer.parseInt(br.readLine());
        visited = new boolean[v + 1]; // 방문배열도 초기화해준다.
        distance = new int[v + 1]; //출발지 ~ 노드 까지 최단거리(비용)을 저장할 배열, 배열인덱스를 노드인데게스와 같게 사용하기 위해서 크기는 v+1
        Arrays.fill(distance, Integer.MAX_VALUE); //거리 배열을 최댓값으로 초기화해둔다.

        for (int i = 0; i < v+1; i++) { //그래프 리스트 초기화 , 리스트인덱스를 노드인덱스와 같게사용하기 위해서 크기는 v+1
            graph.add(new ArrayList<>());
        }

        for (int i = 0; i < e; i++) { //간선의 수만큼, graph 리스트에 값 추가. 출발노드,도착노드,비용 으로 들어온다.
            int[] edgeInfo = Arrays.stream(br.readLine().split(" ")).mapToInt(Integer::parseInt)
                .toArray();
            graph.get(edgeInfo[0]).add(new Node(edgeInfo[1], edgeInfo[2]));
        }

    }
    static void solve() throws IOException {
        dijkstra();
        for (int i = 1; i <= v; i++) {
            if (distance[i] == Integer.MAX_VALUE) {
                bw.write("INF\n");
            } else {
                bw.write(distance[i]+"\n");
            }
        }

    }

    static void dijkstra() throws IOException {
        //우선순위큐를 이용한다. 비용을 정렬기준으로 전달한다.(비용이 낮은것이 우선순위가 높다.)
        PriorityQueue<Node> pq = new PriorityQueue<>( (o1,o2) ->  o1.cost - o2.cost);

        //출발노드는 자기자신에게 가는 비용은 0이므로 0으로 초기화하고 우선순위큐에 넣는다.
        distance[start] = 0;
        pq.add(new Node(start, 0)); // 큐에 넣을때는 (노드인덱스, 해당 인덱스까지 가는 최소비용)로 넣는다.

        while (!pq.isEmpty()) { //우선순위큐가 빌때까지 반복한다.

            Node currentNode = pq.poll();

            if (visited[currentNode.index]) { //방문했던 노드라면 넘어간다. (방문된 노드라면 , distance[해당 노드인덱스] 값은 최소비용이고, 더이상 갱신되지 않는다.
                continue;
            }
            visited[currentNode.index] = true;

            for (Node adjNode : graph.get(currentNode.index)) {
                int adjNodeIndex = adjNode.index;
                int adjNodeCost = adjNode.cost;
                if ( !visited[adjNodeIndex] && distance[adjNodeIndex] > adjNodeCost + distance[currentNode.index]) {
                    distance[adjNodeIndex] = adjNodeCost + distance[currentNode.index];
                    pq.add(new Node(adjNodeIndex, distance[adjNodeIndex]));
                }
            }
        }

    }
    static class Node {
        int index;
        int cost;
        public Node(int index, int cost) {
            this.index = index;
            this.cost = cost;
        }
    }
    
}

어떤 노드가 방문되었다면 그 노드는  출발지 ~ 해당노드 의 최소비용이 확정된 노드이다. 

 

           [최소비용(출발지 ~ 해당 노드까지 비용의 최소값)]

다익스트라 알고리즘은 우선순위큐에서 최소비용의 노드를 골라 인접 노드를 살펴보고, 값을 갱신할게 있으면 갱신시킨후 갱신한 노드 (노드의 인덱스,갱신된 최소비용값)를 우선순위큐에 넣는것을 반복한다.

선택에 순간에서 가장 최소비용인 노드를 택하기 때문에

선택된 노드는 더이상 값이 갱신되지않고 , 그 값은 출발지 ~ 해당 노드까지의 최소비용인 것이다.

 

증명이 나와있는 블로그

[Java]다익스트라 알고리즘(Dijkstra Algorithm)

위의 이유로 인해서 ,

우선순위큐에서 뽑은 노드의 인접노드를 살펴보는 코드에서 이미 방문한 노드는 살펴보지않는다는 코드를 추가했다. 

for (Node adjNode : graph.get(currentNode.index)) {
    int adjNodeIndex = adjNode.index;
    int adjNodeCost = adjNode.cost;
    if ( !visited[adjNodeIndex] && distance[adjNodeIndex] > adjNodeCost + distance[currentNode.index]) {
        distance[adjNodeIndex] = adjNodeCost + distance[currentNode.index];
        pq.add(new Node(adjNodeIndex, distance[adjNodeIndex]));
    }
}

 

1753번: 최단경로

위의 코드로 푼 문제.

인접노드를 살펴볼때 이미 방문한 노드를 살펴보지않게했더니 아주조금 빨라졌다.

2. 방문배열을 사용하지않는 코드 ( 주로 사용)

방문배열없이, 방문 체크는 어떻게해야할까?

public class Main {

    static BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
    static BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));

    static int[] distance;
    static int v,e,start;
    static List<List<Node>> graph;
    static final int maxRange = 3000000;

    public static void main(String[] args) throws IOException {
        input();
        solve();

        bw.flush();
        bw.close();

    }

    static void input() throws IOException {
        int[] input = Arrays.stream(br.readLine().split(" ")).mapToInt(Integer::parseInt).toArray();
        v = input[0];
        e = input[1];
        start = Integer.parseInt(br.readLine());
        distance = new int[v + 1];
        Arrays.fill(distance, maxRange+1);

        graph = new ArrayList<>();
        for (int i = 0; i < v+1; i++) {
            graph.add(new ArrayList<>());
        }
        for (int i = 0; i < e; i++) {
            int[] graphInfo = Arrays.stream(br.readLine().split(" ")).mapToInt(Integer::parseInt)
                .toArray();
            int v1 = graphInfo[0];
            int v2 = graphInfo[1];
            int vCost = graphInfo[2];

            graph.get(v1).add(new Node(v2, vCost));
//            graph.get(v2).add(new Node(v1, vCost));  무방향이거나, 양방향일때 추가
        }

    }
    static void solve() throws IOException {
        dijkstra();

        for (int i = 1; i <= v; i++) {
            int cost = distance[i];
            if (cost == maxRange + 1) {
                bw.write("INF\n");
            } else {
                bw.write(cost+"\n");
            }
        }

    }


    static void dijkstra() {
        PriorityQueue<Node> pq = new PriorityQueue<>((o1, o2) -> o1.cost - o2.cost);
        pq.add(new Node(start, 0));
        distance[start] = 0;

        while (!pq.isEmpty()) {
            Node pqNode = pq.poll(); //우선순위큐에서 뽑힌 노드는 (노드 인덱스 , 출발지에서 해당 노드까지 걸리는 비용)이 저장된 노드

            if (distance[pqNode.index] < pqNode.cost) { //해당 노드에 대한 distance값은 여러번 갱신될 수 있어서 큐에 자주 들어갈 수있지만, 한번 방문됬다면 distance의 값은 최소값이다.
                continue; //distance의 값이 더 작으니까 볼 필요없다 -> 이미 방문된 노드이다.
            }// 값이 같은 순간 => distance값이 갱신되서 큐에 들어갔고, 우선순위상 해당 노드가 지금 뽑혔다.
            // distance값이 더 큰 경우가 생기는 이유 => 시작노드에서는 인접노드를 모두 큐에 넣게 되며 거리값을 갱신한다. 그 이후 다른값으로 갱신되더라도, 시작노드때 큐에 넣어놓은 값은 남아있기 때문이다.
            // 그런값을 무시하기 위해 위와같은 조건문을 붙인다.

			//인접노드를 살펴보고, 출발지에서 인접노드를 바로가는것보다 뽑힌노드를 경유해서 가는게 더 최소비용 인지 체크 
            for (Node adjNode : graph.get(pqNode.index)) { //graph라는 리스트에서 뽑는 노드는 pq노드의 인접노드로 (도착노드, 그 노드로가는 비용)의 간선 정보가 들어있다.
                if(distance[adjNode.index] > distance[pqNode.index] + adjNode.cost ) //지금 distance에 저장된, 출발지->인접노드까지 가는 비용보다, pq노드에 들린후 pq노드에서 인접노드를 가는비용이 더 적으면 갱신
                {
                    distance[adjNode.index] = distance[pqNode.index] + adjNode.cost; //갱신
                    pq.add(new Node(adjNode.index, distance[adjNode.index])); //갱신을 했으면 우선순위큐에서 추가해준다
                }

            }
        }

    }

    static class Node {
        int index;
        int cost;

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



}

중요

우선순위큐에서 뽑는 노드의 비용값은 출발지->해당노드 까지 걸리는 최소비용의 값임을 잊지말자.

 

그래프 간선의 비용과 헷갈리지 말것. ( 변수명을 잘 정하자.)

 

 

1753번: 최단경로

위의 코드로 제출했을때.

 

 

 

다른예제

백준/1504 특정한 최단 경로/ 다익스트라 알고리즘

 

 

★★★ 백준/13549 숨바꼭질3 / bfs, 다익스트라 알고리즘 [미완]

 

 

 

출처,참고,더 자세한 정보

[Algorithm] 다익스트라(Dijkstra) 알고리즘을 Java로 구현해보자! (BOJ-1753 최단경로)

 

[알고리즘/Java]다익스트라(Dijkstra) 알고리즘

 

[Java]다익스트라 알고리즘(Dijkstra Algorithm)