최단거리 구하기 : Dijkstra algorithm 코드로 구현

2021.06.07 - [Java/알고리즘] - 최단경로 구하기 : Dijkstra algorithm

최단경로 구하기 : Dijkstra algorithm

 

 

앞서 한 노드로부터 각 노드 까지 최단 거리를 구하는 Diijkstra 알고리즘에 대해 알아봤다.

 

이번엔 알고리즘을 코드로 구현해보자. 크게 세 가지를 중점으로 작성했다.

 

* 시작 노드를 기준으로 weight 행렬 작성하는 method

   - weight 배열은 djikstra 생성자에서 모두 inf(=9999)로 초기화.

   - 현재 노드를 기준으로! 다른 노드까지의 weight입력

    - 현재 노드와 연결이 되어있는지 and 방문한 곳인지 확인!

  private void baseWeightArray(int current){
        //현재 노드 기준으로 다른 노드 weight입력하기
        for (int j = 0; j < number; j++) {

            if ((matrix[current][j] > 0) && (visited[j] == false)) {

                weight[j] = matrix[current][j];

            }

        }

        System.out.println(start + "노드 기준 weight : " + Arrays.toString(weight));
        System.out.println("---------------------------------------------");
        }

 

* 다음 노드 구하는 method

  다음 노드는 weight배열에서 방문한 노드를 제외하고 weight가 가장 낮은 index(노드)이다.

public int findMinIndex(int current){

    int minIndex=0;
    int minValue = inf;


        for(int i = 0;i< number;i++){

            if((visited[i]==false) &&(weight[i] < minValue)){
                minValue = weight[i];
                minIndex = i;
            }
        }
        System.out.println("다음 노드 : " + minIndex  );
        return minIndex;
    }

 

* 루프를 돌며 weight행렬은 업데이트 하는 method

  - 시작 노드를 주입받는다.

  - 시작 노드를 기준으로 weight 배열 셋팅, 방문여부 등을 업데이트한다.

  - while문 내에서
     현재 노드와 연결되어 있고 && 방문하지 않은 노드에 대해서
     해당 노드에 바로 가는 것보다 현재 노드를 거쳐가는 것이 weight가 작다면 weight배열을 작은 값으로 업데이트

public void shortCutSearch(int start) {
        int current = start;
        weight[current] = 0;
        visitArray.push(current);
        visited[current] = true;
        System.out.println();
        System.out.println(start + "노드로 시작");

        baseWeightArray(current);


        while(visitArray.size() != number){
            //다음 current 정하기
            current = findMinIndex(current);
            visitArray.push(current);
            visited[current] = true;
            System.out.println("visited : " + Arrays.toString(visited));
            //j 로 바로가는거랑, current거쳐서 가는거랑 비교
            for(int j = 0; j<number;j++){

                int temp = weight[current] + matrix[current][j];
                if((matrix[current][j] != 0)
                        && (visited[j]==false)
                        && (  temp < weight[j])){

                    weight[j] = temp;
                }
            }
            System.out.println("weight : " + Arrays.toString(weight));

            System.out.println("---------------------------------------------");

            if(visitArray.size() == number) {
                printResult();
                break;
            }

        }

    }

 

1. Dijkstra Class 전체 코드

package graph;

import java.util.Arrays;
import java.util.Enumeration;
import java.util.Stack;

public class Dijkstra {

    int start;
    int[][] matrix;
    int[] weight;
    int number;
    boolean[] visited;
    Stack<Integer> visitArray;
    int inf = 99999;
    public Dijkstra(int number){
        this.number = number;
        matrix = new int[number][number];
        weight = new int[number];
        visited = new boolean[number];
        visitArray = new Stack<>();

        for(int i=0;i<number;i++){
            weight[i] = inf;
        }
    }


    public void shortCutSearch(int start) {
        int current = start;
        weight[current] = 0;
        visitArray.push(current);
        visited[current] = true;
        System.out.println();
        System.out.println(start + "노드로 시작");

        baseWeightArray(current);


        while(visitArray.size() != number){
            //다음 current 정하기
            current = findMinIndex(current);
            visitArray.push(current);
            visited[current] = true;
            System.out.println("visited : " + Arrays.toString(visited));
            //j 로 바로가는거랑, current거쳐서 가는거랑 비교
            for(int j = 0; j<number;j++){

                int temp = weight[current] + matrix[current][j];
                if((matrix[current][j] != 0)
                        && (visited[j]==false)
                        && (  temp < weight[j])){

                    weight[j] = temp;
                }
            }
            System.out.println("weight : " + Arrays.toString(weight));

            System.out.println("---------------------------------------------");

            if(visitArray.size() == number) {
                printResult();
                break;
            }

        }

    }

    private void baseWeightArray(int current){
        //현재 노드 기준으로 다른 노드 weight입력하기
        for (int j = 0; j < number; j++) {

            if ((matrix[current][j] > 0) && (visited[j] == false)) {

                weight[j] = matrix[current][j];

            }

        }

        System.out.println(start + "노드 기준 weight : " + Arrays.toString(weight));
        System.out.println("---------------------------------------------");
        }

    public int findMinIndex(int current){

    int minIndex=0;
    int minValue = inf;


        for(int i = 0;i< number;i++){

            if((visited[i]==false) &&(weight[i] < minValue)){
                minValue = weight[i];
                minIndex = i;
            }
        }
        System.out.println("다음 노드 : " + minIndex  );
        return minIndex;
    }

    public void printResult(){
        System.out.println("visited : " + visitArray.toString());
        System.out.println(start +" 노드를 기준으로 각 노드까지 최단 거리 : " + Arrays.toString(weight));
    }


}

2. main

graph는 이전에 작성한 너비우선 탐색 글에 사용한 것 과 동일하다.

2021.06.06 - [분류 전체보기] - BFS(Breadth-First Search) 너비 우선 탐색 : 코드로 구현

BFS(Breadth-First Search) 너비 우선 탐색 : 코드로 구현

package graph;

public class DijkstraPractice {

    public static void main(String[] args) {

        int number = 6;
        UndirectedGraph graph = new UndirectedGraph(number);
        Dijkstra dijkstra = new Dijkstra(number);


        graph.addEdge(0,1,1);
        graph.addEdge(0,2,4);
        graph.addEdge(1,2,2);
        graph.addEdge(2,3,1);
        graph.addEdge(3,4,8);
        graph.addEdge(3,5,3);
        graph.addEdge(4,5,4);


        dijkstra.matrix = graph.getMatrix();
        dijkstra.shortCutSearch(0);



    }
}

 

3. 실행 결과

0노드로 시작
0노드 기준 weight : [0, 1, 4, 99999, 99999, 99999]
---------------------------------------------
다음 노드 : 1
visited : [true, true, false, false, false, false]
weight : [0, 1, 3, 99999, 99999, 99999]
---------------------------------------------
다음 노드 : 2
visited : [true, true, true, false, false, false]
weight : [0, 1, 3, 4, 99999, 99999]
---------------------------------------------
다음 노드 : 3
visited : [true, true, true, true, false, false]
weight : [0, 1, 3, 4, 12, 7]
---------------------------------------------
다음 노드 : 5
visited : [true, true, true, true, false, true]
weight : [0, 1, 3, 4, 11, 7]
---------------------------------------------
다음 노드 : 4
visited : [true, true, true, true, true, true]
weight : [0, 1, 3, 4, 11, 7]
---------------------------------------------
visited : [0, 1, 2, 3, 5, 4]
0 노드를 기준으로 각 노드까지 최단 거리 : [0, 1, 3, 4, 11, 7]