다익스트라 , 벨만-포드, 플로이드-워샬 알고리즘 차이

그래프 알고리즘은 주어진 그래프의 정점(Vertex)과 간선(Edge)을 처리하여 다양한 문제를 해결하는 알고리즘입니다. 가장 널리 쓰이는 알고리즘으로 BFS 와 DFS 가 있습니다. 그 중 최단 경로를 찾는 알고리즘으로 BFS 알고리즘을 사용합니다. 하지만 BFS 알고리즘은 간선의 가중치가 항상 일정할 때 사용할 수 있습니다.

간선의 가중치가 다른 경우 최선의 경로를 찾는 알고리즘으로는 다익스트라 , 벨만-포드, 플로이드-워샬 알고리즘이 있습니다.

각각의 차이는 다음과 같습니다.

 

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

주어진 시작 정점에서 다른 모든 정점까지의 최단 경로를 찾습니다.

일반적으로 우선순위 큐를 사용해서 구현합니다.

가중치가 모두 양수인 경우 사용 가능합니다.

시간 복잡도: O((V + E) log V) (우선순위 큐를 사용한 경우)

적용할 수 있는 사례 : 네비게이션 시스템에서 최단 경로 계산, 패킷 전달 경로 최적화, 게임에서 캐릭터 이동 경로 계산

아래는 다익스트라의 핵심 알고리즘입니다. 우선순위큐와 distance 배열을 무한 값으로 초기화 시켜두고 이것을 노드와 노드가 연결 된걸 방문하면서 최단 경로로 수정시켜주는 원리입니다.

 

	int start = 1;
        int[] dist = new int[N + 1];
        Arrays.fill(dist, Integer.MAX_VALUE);
        dist[start] = 0;
        
        PriorityQueue<int[]> pq = new PriorityQueue<>(Comparator.comparingInt(a -> a[1]));
        pq.offer(new int[]{start, 0});
        
        while(!pq.isEmpty()){
            int[] current = pq.poll();
            int node = current[0];
            int cost = current[1];
            
            if(cost > dist[node]) continue;
            
            for(Edge edge : graph.get(node)){
                if(dist[edge.to] > dist[node] + edge.weight){
                    dist[edge.to] = dist[node] + edge.weight;
                    pq.offer(new int[]{edge.to, dist[edge.to]});
                }
            }
        }

다익스트라 알고리즘을 사용한다면 위 같은 결과를 얻을 수 있습니다.

이때 5 → 2 가중치가 1에서 -2 로 변한다면 다음과 같습니다.

 

아직까지 여전히 최단 거리를 계산할 수 있습니다.

하지만 -2보다 좀 더 큰 음수인 -4로 바뀐다면 다익스트라 알고리즘에 대한 결과는 아래 같이 바뀝니다.

 

이렇게 음수 간선의 순환이 생기게 되고 최단 거리가 음의 무한인 노드가 발생하여 그 노드를 통해서 다른 노드를 가게 됐을 때도 -∞ + n 이기 때문에  -∞ 가 됩니다. 따라서 음의 순환 고리가 생길 수 있으므로 다익스트라는 음의 간선 가중치가 있을 땐 사용하지 못합니다.

 

대표 문제

https://www.acmicpc.net/problem/1753

 

 

벨만-포드 알고리즘 (Bellman-Ford Algorithm)

주어진 시작 정점에서 다른 모든 정점까지의 최단 경로를 찾습니다.

모든 간선을 반복적으로 검사하여 최단 거리를 업데이트합니다. N-1번의 반복을 통해 모든 최단 경로를 보장하고, 추가적인 반복을 통해 음수 사이클의 존재를 확인합니다.(이러므로 당연히 다익스트라에서 구할 수 있는 최적의 해를 보장합니다. 대신 다익스트라보다 시간 복잡도가 훨씬 많이 걸리기에 가중치가 양수만 존재한다면 다익스트라 알고리즘을 이용하는 것이 훨씬 경제적입니다.)

• 음의 가중치도 처리할 수 있습니다.
• 추가적인 반복을 통해 음수 사이클의 존재를 감지할 수 있습니다. N번째 반복에서 여전히 거리가 업데이트된다면 음수 사이클이 존재함을 의미합니다.

시간 복잡도: O(V * E) 모든 간선을 N-1번 반복하여 검사하기 때문에 노드 수와 간선 수에 비례하는 시간이 소요됩니다.

단순 리스트 또는 배열 사용하여 구현합니다.

적용할 수 있는 사례 : 금융 모델링, 음수 사이클이 있는 그래프, 금융 시스템에서 무한한 이득을 얻을 수 있는 사이클 감지

핵심 알고리즘은 아래와 같습니다.

	int start = 1;
        long[] dist = new long[N + 1];
        Arrays.fill(dist, Long.MAX_VALUE);
        dist[start] = 0;
        
        // 벨만-포드 알고리즘 실행
        for(int i = 1; i < N; i++) {
            for(Edge edge : edges){
                if(dist[edge.from] != Long.MAX_VALUE && dist[edge.to] > dist[edge.from] + edge.weight){
                    dist[edge.to] = dist[edge.from] + edge.weight;
                }
            }
        }
        
        // 음수 사이클 감지
        boolean negativeCycle = false;
        for(Edge edge : edges){
            if(dist[edge.from] != Long.MAX_VALUE && dist[edge.to] > dist[edge.from] + edge.weight){
                negativeCycle = true;
                break;
            }
        }

 

대표문제

https://www.acmicpc.net/problem/11657

 

 

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

그래프의 모든 정점 쌍 간의 최단 경로를 찾습니다.(단일 시작점 아님 주의)

모든 정점 쌍 간의 최단 경로를 찾을 때사용되고, 음의 가중치를 처리할 수 있지만, 음의 사이클이 없는 경우 사용할 수 있습니다.

플로이드-워샬 알고리즘은 동적 프로그래밍(DP)을 이용해 중간에 경유하는 정점을 점진적으로 늘려가며 최단 경로를 업데이트합니다.

1. 그래프의 모든 정점 쌍 간의 최단 거리를 초기화합니다. 직접 연결된 간선의 거리를 사용하고, 연결되지 않은 경우 무한대로 설정합니다.
2. 각 정점을 중간 정점으로 사용하여 모든 정점 쌍 간의 최단 거리를 갱신합니다.
3. 중간 정점을 통해 더 짧은 경로가 발견되면 최단 거리를 업데이트합니다.

시간 복잡도: O(V^3)

적용할 수 있는 사례 : 모든 쌍 최단 경로 문제(모든 정점 쌍 간의 최단 경로를 찾아야 하는 경우), 네트워크 내 모든 컴퓨터 간의 최단 경로를 찾는 경우, 교통 시스템(도시 간의 모든 경로를 분석하여 최단 경로를 찾는 경우)

핵심 알고리즘은 아래와 같습니다.

 

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

        // 플로이드-워샬 알고리즘
        for (int k = 0; k < N; k++) { // 중간에 경유하는 노드
            for (int i = 0; i < N; i++) { // 시작 노드
                for (int j = 0; j < N; j++) { // 도착 노드
                    if (dist[i][j] > dist[i][k] + dist[k][j]) {
                        dist[i][j] = dist[i][k] + dist[k][j];
                    }
                }
            }
        }

 

대표 문제

https://www.acmicpc.net/problem/11404

 

요약

알고리즘	방향성 그래프	무방향성 그래프	음수 가중치 간선	음수 사이클 감지
다익스트라	가능	가능	불가능	불가능
벨만-포드	가능	가능	가능	가능
플로이드-워샬	가능	가능	가능(음수 사이클 없을 시)	불가능