(basic) Dijkstra, Floyd warshall

 본 포스팅은 블로거가 개발언어의 개념정리 필요를 위한것입니다.

목차와 차례가 뒤죽박죽이며 오직 블로거의 편의목적을 위해 작성되었음을 알려드립니다. 

 

- Dijkstra

- Floyd warshall 

-

 

 

 

- Dijkstra

 

 

위키백과

A -> B 로 갈때 최단 경로의 수를 구하는 알고리즘이다.

 

우선 그전에 가중치에 대해서 알아야한다. 가중치란 꼭짓점과 꼭짓점 사이에 존재하는 변으로 그 위에 비용을 적은 숫자를 말한다.

 

쉽게 말해서 X에서 Y로 갈때 드는 시간, 돈, 에너지와 같이 소모될 비용에 대한 것이다.

 

그리고 이것을 바탕으로 X에서 Y로 가는 가중치에 대하여 최소한의 가중치를 구하는것이 다익스트라 알고리즘이다.

 

쉽게 말해 가장 최단 노선으로 갈경우의 비용을 계산하는것이다.

 

알고리즘 - 

1) 가장 비용이 저렴한 정점을 찾는다.

2) 이 정점의 이웃 정점에 현재 비용보다 싼 경로가 있는 확인후 있다면 가격 수정

3) 모든 이웃정점 확인

4) 결과확인

 

A[][] = 배열로구성된 비용

v[] = 방문했는지 확인할노드

d[] = X -> Y로 갈때의 최적 비용 넣을 배열

 

동빈나님의 블로그 코드 c++입니다. : https://m.blog.naver.com/PostView.nhn?blogId=ndb796&logNo=221234424646&proxyReferer=https%3A%2F%2Fwww.google.com%2F

package dijkstra;

public class _dijkstra{

    static int number = 6;
    static int INF = 10000;

    static int a[][] = new int[][]
    {
        {0, 2, 5, 1, INF, INF},
        {2, 0, 3, 2, INF, INF},
        {5, 3, 0, 3,   1,   5},
        {1, 2, 3, 0,   1, INF},
        {INF, INF, 1, 1, 0 ,2},
        {INF, INF, 5, INF, 2, 0}
    };

    static boolean v[] = new boolean[6];
    static int d[] = new int[6];

    static int getSmallIndex(){
        int min = INF;
        int index = 0;
        for(int i = 0; i < number; i++){
            if(d[i] < min && !v[i]){
                min = d[i];
                index = i;
            }
        }
        
        return index;
    }

    static void dijkstra(int start){
        for(int i = 0 ; i < number ; i++){
            d[i] = a[start][i];
        }
        v[start] = true;

        for(int i = 0 ; i < number -2 ; i++){ // number -2 를 하는이유는
        								// 시작할때 한번 이미 진행했고
                                        // 끝나는 마지막은 할필요가없기때문에
            int current = getSmallIndex();
            v[current] = true;
            for(int j = 0 ; j < 6 ; j++){
                if(!v[j]){
                    if(d[current] + a[current][j] < d[j]){
                        d[j] = d[current] + a[current][j];
                    }
                }
            }
        }
    }


    public static void main(String args[]){
        dijkstra(0);
        for(int i = 0 ; i < number ; i++){
            System.out.print(d[i]+" ");
        }
    }
}

 

 

A, B, C, D 라는 도시가 있다.

A -> D로 가는 가장 싼 경로를 탐색한다고 했을때

A에서 주변검사후 d[]에 다가 갱신

그다음 방문하지 않는노드중 가장 싼경로 -> B 

B에서 주변검사후 d[]에 다가 갱신

C, D 반복한다.

 

이러한 순서대로 하다보면은 가장 싼 경로로 가는방식이 나온다.

이 알고리즘이 왜 이런식으로 하면 답이 나오는지에 대해 알필요가 있는데

그 이유는 A 에서 Z로 갈경우 B 에서 X까지를 검사해서 가장 빠른길을 찾아보았기 때문이다.

그리고 그 순서는 A에서 연결된 B,C를 검사하고 B에서 연결된 D,E,F나 C에서 연결된 G,H와같이 

작은문제를 해결함으로써 큰문제를 해결하는 방식으로 나아간다.

 

이것을 최적화하는 방법으로는 우선순위 큐를 사용하는것이다.

최솟값을 빼오기위해서 하는작업(getSmallIndex())을 큐로 작업하여서 N^2 을 NlogN으로 바꿀수있다.

 

여기서 자세히 설명되어있다. 

(힙 : 자동정렬의 특징)

https://jason9319.tistory.com/307

다익스트라 알고리즘(Dijkstra's Algorithm)

 

 

- Floyd warshall 

 

모든정점에서 모든정점을 계산하는것이다.

다익스트라는 한정점에서 모든점을 계산하는것이다.

시간복잡도 O(N*N*N)을 가진다. 그렇기 때문에 다익스트라보다 느리다고 할수있다.

 

 

코드 동빈나 : 

https://m.blog.naver.com/PostView.nhn?blogId=ndb796&logNo=221234427842&proxyReferer=https%3A%2F%2Fwww.google.com%2F

package dijkstra;

public class _floydwarshall{
    static int number = 4;
    static int INF = 100000000;

    static int a[][] = new int[][]{
        {0,5,INF,8},
        {7,0,9,INF},
        {2,INF,0,4},
        {INF,INF,3,0}
    };

    static void floydwarshall(){

        int d[][] = new int[number][number];

        for(int i = 0 ; i < number ; i++){
            for(int j = 0 ; j < number ; j++){
                d[i][j] = a[i][j];
            }
        }


        for(int k = 0 ; k < number ; k++){
            for(int i = 0 ; i < number ; i++){
                for(int j = 0 ; j < number ; j++){
                    if(d[i][k] + d[k][j] < d[i][j])
                        d[i][j] = d[i][k] + d[k][j];
                }
            }
        }


        for(int i = 0 ; i < number ; i++){
            for(int j = 0 ; j < number ; j++){
                System.out.print(d[i][j]+ " ");
            }
            System.out.println();
        }
    }

    public static void main(String args[]){
        floydwarshall();
    }
}

 

 

핵심 : 거쳐가는것이 더 빠르다면 그것을 값으로 대체해라

이런식으로 하다보면 최종적으로 가장 빠른길이 나온다.

다이나믹프로그래밍 문제라고 하니까 직관적으로 이해가 가능하지만 세세하게는 이해가 가지 않는다.

 

거쳐가는것을 한번만 계산하면 자동적으로 나머지 계산하면서 최종적으로 어느길이 빠른지 결정이 되는것인가