[알고리즘] 최단 경로 알고리즘 - Dijkstra, Bellman-Ford, Floyd-Warshall 알고리즘

 

 

Dijkstra 알고리즘

 

최단 경로(Shortest Path) 찾기는 주어진 가중치 그래프에서 출발점에서 도착점까지의 최단 경로를 찾는 알고리즘이다. 이 최단 경로를 찾는 알고리즘 중 많이 사용하는 것이 바로 Dijkstra 알고리즘이다.

 

Dijkstra 알고리즘은 출발점에서 각 정점까지의 최단 거리 및 경로를 구하는 알고리즘으로 이전에 배웠던 Prim의 MST 알고리즘과 유사하다.

 

어떤 점이 차이가 있냐하면, Prim 알고리즘은 임의의 점에서부터 시작을 하지만, Dijkstra 알고리즘은 출발 지점이 있다. 또한 Prim 알고리즘에서는 배열 D에 간선의 가중치를 저장했지만, Dijkstra 알고리즘은 배열 D에 출발점에서 각 정점까지의 거리를 저장한다. Prim 알고리즘에 관해 궁금하다면, 아래 포스팅을 참고하길 바란다.

 

[알고리즘] 최소 신장 트리(MST) - Kruskal, Prim, Sollin 알고리즘

 

 

 

Dijkstra 알고리즘의 중요한 특징 중 하나는 어느 간선의 가중치라도 음수가 있으면 안된다. 만약 음수가 있다면 최적해를 찾을 수 없는 구조이기 때문이다.

 

 

 

Dijkstra 알고리즘의 동작 방식은 D 배열에 있는 값이 최소인 정점으로 minVertax를 선정하고, 그 minVertex의 이웃 정점들을 갱신해준다.

 

즉, Dijkstra는 한 정점에서 다른 정점까지 가는 최소의 거리를 구해주기 위해 구해주는 것이다. 그렇기 때문에 minVertex 이웃 정점들을 갱신해주고 전체 D 중 최소 값으로 방문한다. prim은 이와 달리 트리를 하나 하나 추가해 주기 때문에 트리의 각 경계 정점에서 이웃한 minVertax를 구하고, D 배열을 갱신하며 트리를 구해주는 것이다.

 

매번 정점을 방문할 때 마다 방문한 정점에 인접한 정점의  거리를 갱신해주는 과정을 간선 완화(Edge Relaxation)이라고 한다.

 

주의할 점은 Dijkstra 알고리즘은 D의 원소 값의 증가 순으로 minVex를 선택하고, 한 번 방문된 정점의 D원소는 갱신하지 않는다. 이에 따라 가중치의 값이 음수가 오는 경우, 최적 값을 찾지 못할 수도 있다.

 

 

 

 

Dijkstra 알고리즘의 구현

 

class DijkstraSP {
    public int N;
    List<Edge>[] graph;
    // 방문 기록 저장 배열
    public int[] previous;
    public DijkstraSP(List<Edge>[] adjList) {
        N = adjList.length;
        previous = new int[N];
        graph = adjList;
    }
    // 최적 경로 구하기
    public int[] shortestPath(int s) {
        boolean[] visited = new boolean[N];
        int[] D = new int[N];
        // 초기화 단계, D 배열은 INF 값으로 초기화
        for(int i =0; i<N; i++) {
            visited[i] = false;
            previous[i] = -1;
            D[i] = Integer.MAX_VALUE;
        }
        // s번 정점부터 시작한다.
        previous[s] = 0;
        D[s] = 0;
        for(int k=0; k<N; k++) {
            int minVertex = -1;
            int min = Integer.MAX_VALUE;
            // 가중치가 가장 작은 인접 정점 방문
            for(int j=0; j<N; j++) {
                if ((!visited[j]) && (D[j] < min)) {
                    min = D[j];
                    minVertex = j;
                }
            }
            // 해당 인접 정점 방문
            visited[minVertex] = true;
            // 인접 정점의 이웃 방문
            for(Edge e : graph[minVertex]) {
            	// 방문 안한 정점 중, 거리 비교(D 배열에 기존에 저장된 거리 vs 현재 정점 거친 거리)
                if (!visited[e.adjvertex]) {
                    int currentDist = D[e.adjvertex];
                    int newDist = D[minVertex] + e.weight;
                    if(newDist < currentDist) {
                        D[e.adjvertex] = newDist;
                        previous[e.adjvertex] = minVertex;
                    }
                }
            }
        }
        return D;
    }
}

 

앞선 Prim 알고리즘을 이해했다면, 익숙하고 어렵지 않은 코드일 것이다. 

 

 

Dijkstra 알고리즘의 수행시간

 

Dijkstra 알고리즘은 n번 반복을 거쳐서 minVertex 값을 찾고, 각 minVertex의 인접하면서 방문되지 않은 정점에 대하여 간선완화를 시도한다. 여기서 minVertex를 찾는 시간 O(n), 그리고 D의 원소를 갱신하는 시간 O(n) 시간이다.

따라서 총 수행 시간은 n * (O(n) + O(n)) = O(n^2) 이다.

 

Dijkstra 알고리즘은 전반적으로 Prim 알고리즘과 구현방법이 비슷하며 수행 시간도 같다. 즉, 이진 힙과 피보나치 힙을 사용할 때도 동일한 수행시간을 가진다.

 

 

 

 

 

 

Bellman-Ford 알고리즘

 

 

Dijkstra 알고리즘은 음수 가중치를 가진 그래프에서 최단 경로를 찾지 못하는 문제가 있었다. Bellman-Ford 알고리즘은 이러한 문제를 해결해준다. 이는 음수 가중치 그래프 내에서도 최단 경로를 찾을 수 있기 때문이다. 그러한 과정이 가능한 이유는 방문하지 않은 정점에서 가중치 값이 가장 작은 정점을 선택하는 Dijkstra와 다르게 동작되서이다.

 

Belleman-Ford 알고리즘은 매 단계마다 모든 간선을 전부 확인한다. 이전의 Dijkstra 알고리즘을 한번 생각해보자. 초기에 인접한 노드 중 가중치의 값이 가장 작은 정점으로 이동하였다. 그리고 이동한 정점에서는 이미 방문한 전의 정점은 제외하고 D 원소를 업데이트 해주었다. 그러나 Bellman-Ford는 다르다. 이미 방문한 전의 정점을 제외하지 않고, 똑같이 D원소를 업데이트 해주는 과정을 거치는 것이다.

 

단, 입력 그래프에 사이클 상의 간선들의 가중치 합이 0보다 작은 음수 사이클이 없어야 한다. 만약 음수 사이클이 존재한다면, 음수 사이클을 반복할 수록 길이가 더 짧아지는 모순이 발생할 수 있기 때문이다.

 

 

 

 

 

Bellman-Ford 알고리즘의 구현

 

 

 

 

public class Main {
    public static final int INF = Integer.MAX_VALUE;
    public static void main(String[] args) {
        int[][] weight = {
                { INF,   1, INF,   2, INF, INF, INF, INF},
                { INF, INF,   4,  -2, INF,   6, INF, INF},
                { INF, INF, INF, INF, INF, INF, INF,   2},
                { INF, INF, INF, INF,  -1, INF, INF, INF},
                { INF, INF, INF, INF, INF, INF,   4, INF},
                { INF, INF,   1, INF, INF, INF, INF, INF},
                { INF, INF,  -1, INF, INF, INF, INF,   1},
                { INF, INF, INF, INF, INF,   3, INF, INF}
        };
        int N = weight.length;

        int s = 0;
        BellmanFord bf = new BellmanFord(N);
        bf.shortestPath(s, weight);
        bf.printPaths(s);
    }
}

class BellmanFord {
    public static final int INF = Integer.MAX_VALUE;
    private int D[];
    private int previous[];
    private int N;

	// 초기화
    public BellmanFord(int numOfVertices) {
        N = numOfVertices;
        D = new int[N];
        previous = new int[N];
    }

	// 최적 경로 탐색
    public void shortestPath(int s, int adjMatrix[][]) {
    	// D 값 초기화
        for(int i=0; i<N; i++) {
            D[i] = INF;
        }
        // s 정점 방문
        D[s] = 0; previous[s] = 0;
        // N-1번(간선의 갯수) 반복
        for(int k=0; k<N-1; k++) {
        	// 값의 탐색(인접 행렬)
            for(int i=0; i<N; i++) {
                for(int j=0; j<N; j++) {
                    if (adjMatrix[i][j] != INF) {
                    	// D[j]는 J정점에서의 기존의 가중치, D[i] + adjMatrix[i][j]는 I 정점을 거친 가중치
                        if (D[j] > D[i] + adjMatrix[i][j]) {
                            D[j] = D[i] + adjMatrix[i][j];
                            previous[j] = i;
                        }
                    }
                }
            }
        }
    }
    public void printPaths(int s) {
        System.out.println("정점 " + s + "으로부터의 최단 거리");
        for (int i = 0; i < N; i++) {
            if (D[i] == INF)
                System.out.println(s + "과 " + i + " 사이에 경로 없음");
            else
                System.out.println("[" + s + ", " + i + "] " + D[i]);
        }
        System.out.printf("\n정점 " + s + "으로부터의 최단 경로\n");
        for (int i = 0; i < N; i++) {
            if (i != s) {
                int back = i;
                System.out.print(back);
                while (back != s) {
                    System.out.print(" <- " + previous[back]);
                    back = previous[back];
                }
                System.out.println();
            }
        }
    }

}

 

 

 

실행 결과는 아래와 같다.

 

 

 

 

Bellman-Ford 알고리즘의 수행 시간

 

Bellman-Ford 알고리즘은 그래프의 인접 행렬을 사용하여 n-1번의 반복을 통해 D[j]를 계산하므로, 수행 시간은 (n-1) * x * O(n) = O(n^3)

 

여기서 인접 리스트를 사용하면 (n-1) * O(m) = O(nm)이 된다.

 

 

 

 

 

 

 

 

 

Floyd-Warshall 알고리즘

 

 

Floyd-Warshall 알고리즘은 이전에 배웠던, Dijkstra 알고리즘이나, Bellman-Ford 처럼 한 정점에서 특정 정점까지의 최단거리를 찾는 알고리즘은 아니다.

 

Floyd-Warshall 알고리즘은 모든 정점 쌍 사이의 최단 경로를 계산하는 알고리즘이다. 즉, 모든 지점에서 모든 지점까지의 최단 거리 배열을 구하는 알고리즘이라고도 할 수 있다.(All Pairs Shortest Paths)

 

모든 쌍의 최단 경로를 찾기 위해서 출발점을 0에서 n-1까지 바꾸어가며, Dijkstra 알고리즘을 수행하는 것으로 모든 쌍의 최단 경로를 찾을 수도 있다. 이 과정에서 만약 인접 행렬을 사용한다면, 수행 시간은 O(n^3)만큼 걸린다. 하지만 Dijkstra 알고리즘에 비해 간단하며, 음수 가중치 그래프에서도 최단 경로를 찾을 수 있다.

 

Dijkstra 알고리즘에서 간선 완화를 했던 부분을 한번 떠올려 보자. 해당 부분에서 우리는 방문한 정점의 인접한 정점을 계속해서 업데이트 해주었다. Floyd-Warshall에서는 이 과정을 출발점을 바꿀 때마다 매번 수행해 주는 것이다. 그렇게 되면, 결국 마지막 출발점 정점에서 간선완화를 완화했을 때 최적의 경로 배열을 찾을 수 있을 것이다.

 

 

 

 

 

 

 

Floyd-Warshall 알고리즘의 구현

 

public class FloydWarshallAlgorithm {
    public static void main(String[] args) {
        int n = 4; // 노드 수
        int[][] adjmatrix = {
            {0, 3, Integer.MAX_VALUE, 7},
            {8, 0, 2, Integer.MAX_VALUE},
            {5, Integer.MAX_VALUE, 0, 1},
            {2, Integer.MAX_VALUE, Integer.MAX_VALUE, 0}
        };

        int[][] D = new int[n][n];

        // 초기화 단계
        for (int i = 0; i < n; i++) {
            for (int j = 0; j < n; j++) {
                D[i][j] = adjmatrix[i][j];
            }
        }

        // 간선 완화 단계
        for (int k = 0; k < n; k++) {
            for (int i = 0; i < n; i++) {
                for (int j = 0; j < n; j++) {
                    if (D[i][j] > D[i][k] + D[k][j]) {
                        D[i][j] = D[i][k] + D[k][j];
                    }
                }
            }
        }

        // 결과 출력
        System.out.println("모든 노드 사이의 최단 경로:");
        for (int i = 0; i < n; i++) {
            for (int j = 0; j < n; j++) {
                if (D[i][j] == Integer.MAX_VALUE) {
                    System.out.print("INF\t");
                } else {
                    System.out.print(D[i][j] + "\t");
                }
            }
            System.out.println();
        }
    }
}

 

Floyd-Warshall 알고리즘의 수행 시간

 

배열 복사에 있어 O(n^2)이 소요되며, for-루프가 3개가 중첩되므로 O(n^3)이다.

즉, 총 수행 시간은 O(n^2) + O(n^3) = O(n^3)

 

Reference

[알고리즘] 다익스트라(Dijkstra) 알고리즘이란? | c++ 다익스트라 구현

[알고리즘] 플로이드 워셜 알고리즘 (Floyd-Warshall Algorithm)