[Algorithm] 최단 경로 알고리즘 3가지

도입

• 최단 경로 문제: 주어진 그래프에서 주어진 두 정점을 연결하는 가장 짧은 경로의 길이를 찾는 문제
  • 가중치가 없는 그래프의 경우, 너비 우선 탐색(BFS)로 찾을 수 있음
  • 가중치가 있다면..? => 다익스트라, 벨만-포드, 플로이드-워셜 등의 알고리즘 필요
• 이러한 알고리즘들은 정점들의 목록을 구해주는 것이 아니라, 최단 경로의 길이를 찾아줄 뿐
  • 실제 경로를 계산하기 위해서는 너비 우선 탐색에서 그랬듯이 탐색 과정에서 별도의 정보를 저장하고, 이것으로부터 실제 경로를 찾아내는 코드를 작성해야 함

음수 간선의 중요성

• 그래프에 대한 최단 경로 문제 해결 시 가장 먼저 유의할 점 => '음수 가중치를 갖는 간선(음수 간선)이 있는지의 여부'
• 왜? => 음수 간선을 지나면 전체 경로의 길이가 짧아지는데, 가중치의 합이 음수인 사이클(음수 사이클)이 존재할 수도 있기 떄문
  • 음수 사이클을 반복해서 돌면, 경로의 길이는 음의 무한대까지 발산 가능.. 즉 끝이 안남
• 음수 사이클이 있을 경우 최단 경로 문제는 제대로 정의되지 않음. 어떤 알고리즘은 의미가 없어지기도 하고, 어떤 알고리즘은 음수 사이클의 존재 여부 정도만 알려줄 수 있음

단일 시작점과 모든 쌍 알고리즘

우리가 다룰 최단 경로 알고리즘들(다익스트라, 벨만-포드, 플로이드-워셜)은 크게 '단일 시작점 알고리즘'과 '모든 쌍 알고리즘'으로 나뉨

• 단일 시작점 알고리즘: 너비 우선 탐색과 비슷하게, 하나의 시작점에서 다른 모든 정점까지 가는 최단 거리를 구함
  • 대표적으로 다익스트라 알고리즘과 벨만-포드 알고리즘이 있음
• 모든 쌍 알고리즘: 모든 정점의 쌍에 대해 최단 거리를 계산
  • 수행 결과는 VXV 크기의 배열, 이 배열의 각 원소는 두 정점 사이의 최단 거리를 나타냄
  • 대표적으로 플로이드-워셜 알고리즘이 있음

방향 그래프와 무향 그래프

• 우리가 다룰 알고리즘은 모두 '방향 그래프'를 기준으로 동작
• => 무향 그래프가 주어진 경우, 양방향 간선을 두 개의 일방 통행 간선으로 쪼개어 방향 그래프로 만들어야 함
• 그러나, 음수 가중치가 있는 무향 그래프의 경우, 이와 같은 기법 사용 불가
  • 무향 음수 간선을 두 개로 쪼개면 이 둘만으로 음수 사이클이 생겨버리기 때문
• => 음수 간선이 있는 무향 그래프에서는 항상 최단 경로 문제를 해결할 수 없음..

다익스트라 알고리즘

• 다익스트라 알고리즘(dijkstra algorithm): 단일 시작점 최단 경로 알고리즘으로, 시작 정점 s에서부터 다른 정점들까지의 최단 거리를 계산

우선순위 큐를 사용하는 너비 우선 탐색

• 다익스트라 알고리즘은 '너비 우선 탐색 + 우선순위 큐'의 형태를 가진다
  • 시작점에서 가까운 순서대로 정점을 방문
  • 우선순위 큐에 '(정점의 번호) + (지금까지 찾아낸 해당 정점까지의 최단 거리)'를 쌍으로 넣기
• 우선순위 큐는 정점까지의 최단 거리를 기준으로 정점을 배열함으로써, 아직 방문하지 않은 정점 중 시작점으로부터의 거리가 가장 가까운 점을 찾는 과정을 간단하게 만들어줌
• 과정
  • 각 정점까지의 최단 거리를 저장하는 배열 dist[]를 유지하며, 정점을 방문할 때마다 인접한 정점을 모두 검사
  • 간선 (u,v) 검사 시 아직 방문하지 않았다면
    • u까지의 최단 거리에 (u, v)의 가중치를 더해 v까지의 경로의 길이를 찾은 후
    • 이 값이 우리가 지금까지 찾은 최단 거리보다 짧다면 dist[v]를 갱신하고 (dist[v], v)를 큐에 넣음
• 큐에 넣음(새로운 정점을 방문함)으로써 각 정점까지의 최단 경로가 새롭게 갱신될 수 있음
  • 즉, 이미 v에 대한 값이 큐에 들어있는데, 더 짧은 경로 정보가 들어올 수 있음
  • 이 경우, 기존값은 그대로 두고 나중에 큐에서 이 값이 꺼내질 때 무시하는 방식을 취함
    • if(dist[u] < cost) continue

구현

public class DijkstraWithPQ {

    static final int INF = Integer.MAX_VALUE;

    static ArrayList<Node>[] graph;
    static int[] dist;

    public DijkstraWithPQ(int V) {
        graph = new ArrayList[V];
        dist = new int[V];

        for (int i = 0; i < V; i++) {
            graph[i] = new ArrayList<>();
            dist[i] = INF;
        }
    }

    public static void dijkstra(int src) {
        dist[src] = 0;

        PriorityQueue<PqForm> pq = new PriorityQueue<>();
        pq.add(new PqForm(src, 0));

        while (!pq.isEmpty()) {
            PqForm curr = pq.poll(); // (방문)
            int here = curr.index; // 현재 정점
            int cost = curr.dist; // 현재 까지의 최단 거리

            // 이미 방문한 정점 처리
            // 만약 지금 꺼낸 것보다 더 짧은 경로를 알고 있다면 지금 꺼낸 것을 무시한다
            if (dist[here] < cost) continue;

            for (int i = 0; i < graph[here].size(); i++) {
                Node next = graph[here].get(i);
                int nextDist = next.weight + cost; // 현재까지의 최단 거리에 방문할 정점의 가중치를 더해 방문점까지의 경로 길이를 구함
                // 더 짧은 경로를 발견하면, dist[]를 갱신하고 우선순위 큐에 넣는다 (발견)
                if (dist[next.x] > nextDist) {
                    dist[next.x] = nextDist;
                    pq.add(new PqForm(next.x, nextDist));
                }
            }

        }
    }

    // 그래프의 정점을 가중치와 함께 표현하기 위한 클래스
    static class Node {
        int x;
        int weight;

        public Node(int x, int weight) {
            this.x = x;
            this.weight = weight;
        }
    }

    // 우선순위 큐에 들어갈 데이터의 클래스
    // index: 정점의 번호
    // dist: 지금까지 찾아낸 해당 정점까지의 최단 거리
    static class PqForm implements Comparable<PqForm> {
        int index, dist;

        PqForm(int index, int dist) {
            this.index = index;
            this.dist = dist;
        }

        // 우선순위 큐에서 dist를 기준으로 배열하기 위해 compareTo 구현
        @Override
        public int compareTo(PqForm o) {
            // dist 기준 오름차순 정렬
            return this.dist - o.dist;
        }
    }

    public void addEdge(int from, int to, int weight) {
        graph[from].add(new Node(to, weight));
    }

    public static void main(String[] args) {
        int V = 5; // 정점의 개수
        int src = 0; // 시작 정점
        DijkstraWithPQ dijkstra = new DijkstraWithPQ(V);

        // 그래프 추가
        dijkstra.addEdge(0, 1, 10);
        dijkstra.addEdge(0, 2, 3);
        dijkstra.addEdge(1, 2, 1);
        dijkstra.addEdge(1, 3, 2);
        dijkstra.addEdge(2, 1, 4);
        dijkstra.addEdge(2, 3, 8);
        dijkstra.addEdge(2, 4, 2);
        dijkstra.addEdge(3, 4, 7);
        dijkstra.addEdge(4, 3, 9);

        // 다익스트라 실행
        dijkstra.dijkstra(src);

        // 결과 출력
        System.out.println("Vertex\tDistance from Source");
        for (int i = 0; i < V; i++) {
            System.out.println(i + "\t\t" + dist[i]);
        }
    }
}

시간 복잡도

• 각 정점마다 인접한 간선들을 모두 검사하는 작업
  • 각 정점은 정확히 한 번씩 방문되고, 모든 간선은 한 번씩 검사되므로
  • 이 작업의 시간 복잡도는 O(|E|)
• 우선순위 큐에 원소를 넣고 적재하는 작업
  • 큐의 최대 크기는 O(|V|)인데, dist[]를 갱신할 때마다 원소를 우선순위 큐에 넣으므로 그보다 많은 원소들이 들어갈 수 있음
  • 때문에 우선순위 큐의 최대 크기는 O(|E|)로 간선의 수만큼 들어갈 수 있음
  • 이 경우 우선순위 큐에 원소 추가/삭제 작업은 O(lg|E|)의 시간이 걸리므로
  • 이 작업의 전체 시간 복잡도는 O(|E|lg|E|)
• 위 두 작업에 걸리는 시간을 더하면 O(|E| + |E|lg|E|) = O(|E|lg|E|)
• 대개의 경우, 그래프에서 간선의 개수 |E| < |V|^2 임
• 사실상 O(lg|E|) = O(lg|V|)이므로 시간복잡도는 O(|E|lg|V|)

실제 경로 찾기

• 그래프를 탐색하는 과정에서 스패닝 트리를 계산한 후, 스패닝 트리를 거슬러 올라가며 경로를 찾는 함수를 구현하면 됨
• 너비 우선 탐색에서의 코드와 비슷함

우선순위 큐를 사용하지 않는 다익스트라 알고리즘

• 정점의 수가 적거나 간선의 수가 매우 많은 경우, 우선순위 큐를 사용하지 않고 반복문을 이용한 방식이 더 빠른 경우가 있음
• 다음 방문할 정점을 우선순위 큐에 보관하는 대신, 매번 반복문을 이용하여 방문하지 않은 정점 중 dist[i]가 가장 작은 값을 찾는 방식
  • => 각 정점의 방문 여부를 나타내기 위해 visited[] 배열 유지 필요
• 시간 복잡도는 O(|V|^2 + |E|)

public class Dijkstra {

    static final int INF = Integer.MAX_VALUE;

    static int V;
    static ArrayList<Node>[] graph;
    // 시작점에서 i 정점까지의 최단 거리
    static int[] dist;
    // i 정점 방문 여부
    static boolean[] visited;

    public Dijkstra(int V) {
        this.V = V;
        graph = new ArrayList[V];
        dist = new int[V];
        visited = new boolean[V];

        for (int i = 0; i < V; i++) {
            graph[i] = new ArrayList<>();
            dist[i] = INF;
        }
    }

    public static void dijkstra(int src) {
        dist[src] = 0;

        while (true) {
            int closest = INF;
            int here = -1;

            // 아직 방문하지 않은 정점 중 가장 가까운 정점을 찾는다
            for (int i = 0; i < V; i++) {
                if (dist[i] < closest && !visited[i]) {
                    here = i;
                    closest = dist[i];
                }
            }

            // 모두 방문했다면 반복문을 빠져나간다
            if (closest == INF) break;

            // 아직 방문하지 않은 인접한 정점을 방문한다
            visited[here] = true;

            for (int i = 0; i < graph[here].size(); i++) {
                Node next = graph[here].get(i);
                if (visited[next.x]) continue;
                int nextDist = next.weight + dist[here]; // 현재까지의 최단 거리 + 다음 정점으로의 가중치
                // dist[next.x] = 시작점에서 다음 정점까지의 최단 거리
                dist[next.x] = Math.min(dist[next.x], nextDist);
            }
        }
    }

    static class Node {

        int x;
        int weight;

        public Node(int x, int weight) {
            this.x = x;
            this.weight = weight;
        }
    }

    public void addEdge(int from, int to, int weight) {
        graph[from].add(new Node(to, weight));
    }

    public static void main(String[] args) {
        int V = 5; // 정점의 개수
        int src = 0; // 시작 정점
        Dijkstra dijkstra = new Dijkstra(V);

        // 그래프 추가
        dijkstra.addEdge(0, 1, 10);
        dijkstra.addEdge(0, 2, 3);
        dijkstra.addEdge(1, 2, 1);
        dijkstra.addEdge(1, 3, 2);
        dijkstra.addEdge(2, 1, 4);
        dijkstra.addEdge(2, 3, 8);
        dijkstra.addEdge(2, 4, 2);
        dijkstra.addEdge(3, 4, 7);
        dijkstra.addEdge(4, 3, 9);

        // 다익스트라 실행
        dijkstra.dijkstra(src);

        // 결과 출력
        System.out.println("Vertex\tDistance from Source");
        for (int i = 0; i < V; i++) {
            System.out.println(i + "\t\t" + dist[i]);
        }
    }
}

벨만-포드 알고리즘

• 다익스트라 알고리즘은 굉장히 유용하지만, 음수 간선이 있는 그래프의 경우 그 정당성이 보장되지 않음..
• 벨만-포드(Bellman-Ford)의 최단 경로 알고리즘은 이러한 음수 간선 문제를 해결하는 알고리즘
• 벨만-포드 알고리즘
  • 다익스트라 알고리즘과 같은 단일 시작점 최단 경로 알고리즘이지만, 음수 간선이 있는 그래프에 대해서도 최단 경로를 찾을 수 있으며, 그래프에 음수 사이클이 있어서 최단 거리가 제대로 정의되지 않는 경우 이것도 알려줌
  • 시작점에서 각 정점까지 가는 최단 거리의 상한을 적당히 예측한 뒤, 예측 값과 실제 최단 거리 사이의 오차를 반복적으로 줄여가는 방식으로 동작
  • 각 정점까지의 최단 거리의 상한을 담은 upper[] 배열을 유지하고, 이 값은 알고리즘이 진행됨에 따라 점점 줄어들어 종료 시에는 실제 최단 거리를 담게 됨

벨만-포드의 동작 과정

• 시작점에서 시작점까지의 최단 거리는 0이므로, upper[s] = 0
• 나머지 원소들에 대한 정보는 없으므로, 모두 upper 값을 최대값으로 초기화 ex) upper[i] = 987654321
• 시작점에서 u와 v까지의 최단 거리 dist[u]와 dist[v]에 대해 다음 조건은 항상 참이다

dist[v] <= dist[u] + w(u, v)

• 이를 이용하여 upper[u] + w(u, v) < upper[v]인 상황에서, upper[v] = upper[u] + w(u, v)로 완화시킬 수 있음
  • u까지의 최단 거리는 항상 upper[u]이거나 이보다 짧음
  • => 그 뒤에 (u, v)를 붙인 경로의 길이는 최대 upper[u] + w(u, v)
  • => 예측값인 upper[v]는 최소 upper[u] + w(u, v)일 것이므로 이 값으로 줄일 수 있는 것 = 완화(relax)
• 위와 같은 완화 과정을 모든 간선에 대해 반복적으로 실행하여 upper를 계속해서 줄이고 원하는 최단 거리에 가깝게 만드는 것

종료 조건

그렇다면 대체 몇 번이나, 어떤 순서로 완화를 해야할까?

• 모든 간선에 대해 완화를 시도하는 작업을 x번 반복하면 x개 이하의 간선을 사용하는 최단 경로들을 전부 찾을 수 있음
  • 자세한 정당성 증명은 책을 참고
• => 모든 간선이 전부 '완화 실패'할 때까지 반복하면 모든 최단 경로를 찾을 수 있음
• 최단 경로는 최대 |V|개의 정점을 갖기 때문에 잘해야 |V| - 1개이 간선을 포함할 것
  • => 모든 간선에 대한 완화 과정은 최대 |V|-1번이면 충분
• 벨만-포드 알고리즘은 음수 간선이 존재하는 경우에도 최단 거리를 올바르게 계산해낼 수 있음

음수 사이클의 판정

• 벨만-포드 알고리즘도 '음수 사이클'이 존재할 경우 예외 없이 의미없는 값을 반환함..
• 하지만, 벨만-포드 알고리즘은 간단한 변형을 통해 음수 사이클의 존재 여부를 판정하도록 할 수 있음
  • 실제로 벨만-포드 알고리즘은 최단 경로의 계산보다는 음수 사이클 존재 여부 판정 용도로 주로 사용됨
• 음수 사이클 판정을 위해 |V|-1번 완화를 시도하는 것이 아니라, |V|번 완화를 시도하자
  • 그래프에 음수 사이클이 없다면 |V|-1번만의 반복으로 모든 최단 거리를 찾아낼 수 있기 때문에, 마지막 반복의 완화는 전부 실패할 것
  • 반면, 음수 사이클이 있다면, |V|번째 반복에서도 항상 완화가 한 번은 성공할 것
• 마지막 반복에서도 완화가 성공했을 경우, 음수 사이클이 존재함을 알 수 있음
• 시간 복잡도는 O(|V||E|)

public class BellmanFord {

    static ArrayList<Node>[] graph;
    static int V;

    public BellmanFord(int V) {
        this.V = V;
        graph = new ArrayList[V];
        for (int i = 0; i < V; i++) {
            graph[i] = new ArrayList<>();
        }
    }

    public static int[] bellmanFord(int src) {
        int[] upper = new int[V];
        Arrays.fill(upper, Integer.MAX_VALUE);
        upper[src] = 0;

        boolean updated = false;

        // V번 순회
        for (int iter = 0; iter < V; iter++) {
            updated = false;

            // 모든 정점에 대하여 완화 수행
            for (int curr = 0; curr < V; curr++) {
                // 인접한 정점들을 업데이트 할 수 있는지 (완화 과정)
                for (int i = 0; i < graph[curr].size(); i++) {
                    Node next = graph[curr].get(i);
                    // (curr, next) 완화 시도
                    if (upper[next.x] > upper[curr] + next.weight) {
                        // 성공
                        upper[next.x] = upper[curr] + next.weight;
                        updated = true;
                    }
                }
            }
            // 모든 간선에 대해 완화가 실패했을 경우, V-1번도 돌 필요 없이 곧장 종료
            // 이미 모든 최단 경로 길이를 찾음
            if (!updated) break;
        }

        // V번째 순회에서도 완화가 성공했다면 음수 사이클이 있음
        if (updated) upper = new int[V];
        return upper;
    }

    static class Node {
        int x;
        int weight;

        public Node(int x, int weight) {
            this.x = x;
            this.weight = weight;
        }
    }
}

실제 경로 계산

• 각 정점을 마지막으로 완화시킨 간선들을 모으면 스패닝 트리를 얻을 수 있음
• 각 정점에서부터 스패닝 트리의 루트인 시작점까지 거슬러 올라가는 경로 = 시작점에서 해당 경로의 최단 경로
  • 각 정점을 마지막으로 완화시킨 간선들은 항상 최단 경로 위에 있기 때문

s에서 v로 가는 경로가 존재하는지 확인하는 법

• 벨만 포드 알고리즘 종료 후, v까지의 경로가 있는지 확인하기 위해 upper[v] = INF인지를 조사해서는 안됨
• 음수 가중치가 있는 경우, upper 값은 경로가 존재하지 않더라도 그 값이 변경될 수 있음
• => upper[v] < INF - 충분히 큰 값인지를 확인해야 함!

사이클이 존재할 경우 최장 경로 구하기

• 주어진 그래프의 가중치의 부호를 모두 바꾼 후 최단 경로를 구하면 사실상 최장 경로를 구한 것이라고 볼 수 있음
• 유의할 점은 일반적으로 이야기하는 최장 경로는 아님
  • 일반적인 최장 경로 문제는 사이클을 포함하지 않는 경로, 즉 단순 경로를 찾기를 요구함
  • 이러한 단순 최장 경로를 찾는 문제는 NP-완전 문제

플로이드-워셜 알고리즘

• 모든 정점 쌍에 대해 둘 사이의 최단 거리를 구해야 하는 경우, 플로이드-워셜 알고리즘을 사용하자
  • 다익스트라 알고리즘이나 벨만-포드 알고리즘을 모든 정점에 대해 수행하여 구할 수도 있지만, 너무 느리다
• 모든 정점 쌍의 최단 거리를 저장하는 2차원 배열 dist[][]를 계산
  • dist[u][v]: 정점 u에서 v로 가는 최단 거리를 의미

정점의 경유점들

플로이드 워셜 알고리즘의 동작 과정을 이해하기 위해서는 경로의 '경유점' 개념을 이해해야 한다

• 두 정점 u, v를 잇는 어떤 경로가 있을 때, 이는 u와 v를 직접 이을 수도 있겠지만 다른 정점들을 지나쳐 갈 수도 있음
  • 직접 연결하는 간선이 없거나, 다른 정점을 경유하는 편이 더 거리가 짧을 경우
  • 경로가 거쳐가는 정점들을 '경유점'이라고 하자
• 정점 집합 S에 포함된 정점만을 경유점으로 사용해 u에서 v로 가는 최단 경로의 길이가 있다고 하자.
  • S에 포함된 모든 정점을 사용할 수 있는 것이지, 실제로 사용할 필요는 없다.
    • 떄문에 사용하는 정점 집합이 다르더라도 최단 경로의 길이는 같을 수 있다. ex) S1 집합에 대한 최단 경로와 S2 집합에 대한 최단 경로가 같을 수 있음
  • 두 정점 사이를 잇는 가장 짧은 간선의 길이 w(u, v)는 공집합에 대한 최단 경로의 길이라고 볼 수 있음
• 우리는 최종적으로 전체 정접 집합 V를 모두 경유점으로 쓸 수 있는 최단 경로의 길이를 구하고 싶다.
• 정점 집합 S에 대한 u에서 v로의 최단 경로를 알고있다고 가정
  • S에 속한 정점 중 하나를 x라고 하면, 최단 경로는 x를 경유했을 수도, 안 했을 수도 있다
  • 경로가 x를 경유하지 않는 경우: S-{x}에 포함된 정점들만을 경유점으로 사용
  • 경로가 x를 경유하는 경우: 이 경로를 (u, x)와 (x, v)로 나눌 수 있음
    • 이 두개의 부분 경로들은 각각 u와 x, x와 v를 잇는 '최단 경로'들이어야 함
    • 당연하게도 두 개의 부분 경로들은 x를 경유하지 않으며, 따라서 S-{x}에 포함된 정점들만으로 경유점으로 사용
  • => 정점 집합 S에 대한 u에서 v로의 최단 경로는 위 두 가지 중 더 짧은 경로가 될 것
  • => 재귀적으로 정의할 수 있음

플로이드-워셜 알고리즘의 프로토타입

• 정점 집합 S_k를 {0, 1, 2, ..., k}와 같이 0번 정점부터 k번 정점까지 포함한 정점 집합이라고 하자
• C_k(u, v)는 0번 정점부터 k번 정점까지만을 경유점으로 썼을 때 u에서 v까지의 최단 경로의 길이
• C_k(u, v) = C_k-1(u, k) + C_k-1(k, v)와 C_k-1(u, v) 중 최솟값
  • C_k의 모든 값이 C_k-1에 의존하는 형태로 변경됨
  • => 반복적 동적 계획법으로 쉽게 해결 가능
  • 코드로 구현하면 C_k(u, v)는 C[k][u][v]에 저장됨

void prototype() {
    // C[0]을 초기화
    for (int i = 0; i < V; i++) {
        for (int j = 0; j < V; j++) {
            if(i != j) C[0][i][j] = Math.min(graph[i][j], graph[i][0] + graph[0][j]);
            else C[0][i][j] = 0;
        }
    }

    // C[k-1]이 있으면 C[k] 계산 가능
    for (int k = 1; k < V; k++) {
        for (int i = 0; i < V; i++) {
            for (int j = 0; j < V; j++) {
                C[k][i][j] = Math.min(C[k - 1][i][j], C[k - 1][i][k] + C[k - 1][k][j]);
            }
        }
    }
}

• 두 정점 사이의 간선이 없는 경우 아주 큰 값을 넣어둠 (graph[i][j] = INF)
• C[0]을 계산할 때, C[0][u][u]는 항상 0으로 초기화
• 시간 복잡도는 3중 for문이 지배하므로, O(|V|^3)

메모리 사용량 줄이기

• 슬라이딩 윈도우 기법을 사용하면 사용하는 배열의 크기를 O(|V|^2)로 줄일 수 있음
• C[k]의 답은 C[k-1]만 있으면 계산할 수 있다는 점에서 착안
  • C[k-2], C[k-3] 등은 계속해서 들고 있을 필요가 없음
  • => C_k(u, v)의 값을 C[k%2][u][v]에 저장하여 배열의 크기를 2 x |V| x |V|로 줄일 수 있음
• 여기서 한 발짝 더 나아가, 별도의 배열을 사용하지 않고 그래프의 가중치를 담는 인접행렬 위에서 곧장 점화식의 결과를 계산하여 더 최적화 가능
  • 사실상 C_k-1(u, v)와 C_k(u, v)가 완전히 동일하기 때문
  • => C[k%2]와 C[(k-1)%2]를 구분할 필요가 없음
  • => 이 둘을 한 개의 2차원 배열에 섞어 써도 됨
  • => 별도의 배열 C를 만들지 않고 인접 행렬 graph에 최단 거리를 계산
• 시간 복잡도는 O(|V|^3) 그대로고, 공간 복잡도는 O(|V|^2)로 줄었음

public class Floyd {
    static final int INF = 987654321;
    // 정점의 개수
    static int V;

    // 그래프의 인접 행렬 표현
    // graph[u][v] = u에서 v로 가는 간선의 가중치. 간선이 없으면 아주 큰 값 넣기
    static int[][] graph;

    public Floyd() {
        graph = new int[V][V];

        for (int i = 0; i < V; i++) {
            Arrays.fill(graph[i], INF);
        }
    }

    void floyd() {
        for (int i = 0; i < V; i++) graph[i][i] = 0;

        for (int k = 0; k < V; k++) { // 경유점
            for (int i = 0; i < V; i++) { // 시점
                for (int j = 0; j < V; j++) { // 종점
                    graph[i][j] = Math.min(graph[i][j], graph[i][k] + graph[k][j]);
                }
            }
        }
    }
}

플로이드-워셜 알고리즘의 최적화

• 플로이드 알고리즘의 동작 시간이 아슬아슬할 경우, 두 번째 for문 바로 다음에 i에서 k로 가는 경로가 실제 있는지 확인하고 만약 경로가 없다면 j에 대한 for문을 수행하지 않도록 하여 최적화 할 수 있음
• 이는 간선이 적을 수록 효과적이며, 경우에 따라 10%에서 20%까지 수행 시간 단축 가능

void floyd() {
    for (int i = 0; i < V; i++) graph[i][i] = 0;

    for (int k = 0; k < V; k++) { // 경유점
        for (int i = 0; i < V; i++) { // 시점
            if(graph[i][k] == INF) continue;
            for (int j = 0; j < V; j++) { // 종점
                graph[i][j] = Math.min(graph[i][j], graph[i][k] + graph[k][j]);
            }
        }
    }
}

실제 경로 계산하기

• 실제 경로를 계산하기 위해 각 정점의 쌍 u, v에 대해 마지막으로 graph[u][v]를 갱신했을 때 사용했던 k의 값을 저장해두면 됨
  • 이 정점의 번호를 w라고 할 때, 이 정점을 경유하니까 graph[u][v]가 최소치가 되었다는 말은 u에서 v로 가는 최단 경로가 경유점 k를 지난다는 의미
• 따라서 재귀 호출을 통해 u에서 w로 가는 최단 경로를 찾고, w에서 v로 가는 최단 경로들을 찾은 뒤 이 둘을 합치면 u에서 v까지의 최단 경로를 얻을 수 있음
  • (u, v) 최단 경로 = (u, w) 최단 경로 + (w, v) 최단 경로 과정을 재귀적으로 호출
• 각 경유점을 저장하기 위해 via[][] 배열을 유지함으로써 O(|V|^2)의 메모리가 추가됨

public class Floyd {

    static final int INF = 987654321;
    // 정점의 개수
    static int V;

    // 그래프의 인접 행렬 표현
    // graph[u][v] = u에서 v로 가는 간선의 가중치. 간선이 없으면 아주 큰 값 넣기
    static int[][] graph;

    // via[u][v] = u에서 v로 가는 최단 경로가 경유하는 점 중 가장 번호가 큰 점
    // -1로 초기화
    static int[][] via;

    public Floyd() {
        graph = new int[V][V];
        via = new int[V][V];

        for (int i = 0; i < V; i++) {
            Arrays.fill(graph[i], INF);
            Arrays.fill(via[i], -1);
        }
    }

    void floyd2() {
        for (int i = 0; i < V; i++) graph[i][i] = 0;

        for (int k = 0; k < V; k++) { // 경유점
            for (int i = 0; i < V; i++) { // 시점
                for (int j = 0; j < V; j++) { // 종점
                    if (graph[i][j] > graph[i][k] + graph[k][j]) {
                        via[i][j] = k; // 마지막으로 갱신한 k값 저장
                        graph[i][j] = graph[i][k] + graph[k][j];
                    }
                }
            }
        }
    }

    // u에서 v로 가는 최단 경로를 계산해 path에 저장
    void reconstruct(int u, int v, List<Integer> path) {
        if (via[u][v] == -1) { // u에서 v로 가는 최단 경로에 경유점이 없는 경우
            path.add(u);
            if (u != v) path.add(v);
        } else {
            int w = via[u][v];
            reconstruct(u, w, path);
            path.remove(path.size() - 1); // reconstruct를 두 번 호출하여 w가 중복으로 들어가므로 하나 지움
            reconstruct(v, w, path);
        }
    }
}

도달 가능성 확인하기(경로 존재 여부 확인)

• 플로이드 알고리즘의 유명한 사용 예로 '가중치 없는 그래프에서 각 정점 간의 도달 가능성 여부를 계산하는 것'이 있음
  • 모든 정점 쌍 u, v에 대해 u에서 v로 가는 경로가 있는지 확인하는 것
• 이는 C_k(u, v)의 정의를 0번부터 k번 정점까지를 경유점으로 사용 가능할 때, u에서 v로 가는 경로가 있는지 여부를 나타내도록 변경하면 쉽게 구할 수 있음.
  • C_k(u, v) = C_k-1(u, v) || (C_k-1(u, k) && C_k-1(k, v))
  • 최소치를 구하는 min 연산을 or 연산으로 바꾸고, 덧셈 연산을 and 연산으로 바꿨을 뿐

public static void calcReachable() {
    for (int i = 0; i < V; i++)
        reachable[i][i] = true;

    for (int k = 0; k < V; k++)
        for (int i = 0; i < V; i++)
            for (int j = 0; j < V; j++)
                reachable[i][j] = reachable[i][j] || (reachable[i][k] && reachable[k][j]);
}