최단경로

모든 출발지 - 목적지 쌍의 최단 경로를 구하는 알고리즘
한 번 돌리고 나면 일종의 최단 경로 사전이 만들어진다고 볼 수 있다.

가중치가 있다면

양의 가중치만 있다면

Dijkstra

• 방문했던 정점을 다시 보지 않는다(Greedy).
• 음의 가중치가 있다면 이미 방문한 정점을 방문해야 비용이 최소가 되기도 한다.
  즉 음의 가중치가 존재할 수 있다면 Dijkstra는 correctness가 보장되지 않는다.
  

음의 가중치도 있다면

• Bellman-ford

가중치가 없다면

그냥 BFS

모든 쌍 최단경로

1. 바로 가는 경로
2. 경유지를 통해 가는 경로

를 모두 비교해봐야 함

그냥 플로이드-워셜(음의 가중치가 있어도)

Brute-force

1. 한 정점으로부터 다른 정점까지의 모든 경로를 구한다.
2. 그 경로들 중 최단 경로를 찾는다.

$n$개의 정점을 갖는 완전 그래프라면

1. 정점 $i$에서 $j$로 가는 경로 중 모든 정점을 한 번씩 거쳐 가는 경로는 반드시 포함되므로, 그 경로의 수만 count한다.
2. $i$에서 출발해 처음 도착할 수 있는 정점의 수는 $n-2$고, 그 중 하나를 선택하면 그 다음 선택할 수 있는 정점의 수는 $n-3$
   → 총 경로의 수는 $(n - 2)\times(n - 3)\times\cdots \times1 = (n - 2)!$

시간 복잡도가 팩토리얼로 나온다 ≡ 사실상 사용 불가능

DP

효율적으로 풀려면

• 모든 정점을 시작 정점으로 해 Dijkstra algorithm을 수행한다.
• 인접 행렬 기준으로 $O(n^3)$ 나온다($n$은 정점의 수).
• 사실 이 방법이랑 플로이드 워셜이랑 시간 복잡도는 비슷한데 구현이 훨씬 간단해서 효율적인 것

$n$이 크면

$n$이 $1000$만 돼도 $(10^3)^3=10^9$회의 연산이 발생한다.
그래서 $n$이 크다면 인접 리스트 + Priority queue + Dijkstra로 (출발지 바꿔 가면서) 돌리는 게 낫다.
대충 $n \le 10^2$ 일 때까지만 쓸 만 한 듯.

Floyd-Warshall

• 모든 node 쌍에 대해 최단 경로를 찾는다.
• Dynamic programming 기법이 쓰인다.
• $O(n^3)$이긴 한데 구현이 Dijkstra보다 훨씬 간단하다.
• 기본적으로 모든 쌍 간의 경로가 존재하는지 찾는 알고리즘에서 출발했기 때문에
  최단 경로 뿐만 아니라 경로 존재 여부를 구하는 문제에도 쓰일 수 있다.
  (최단 경로를 구했다 ≡ 비용이 계산됐다 ≡ 경로가 존재한다)
• 그냥은 못 가도 다른 정점을 경유해서 갈 수 있다면 경로가 존재하는 것으로 간주한다.
• 모든 node 쌍에 대해 경유 가능한 정점을 하나씩 추가해 고려하며 최단 경로를 계산한다.

Pseudocode

allPairsShortest(d[1..n][1..n]):
  FOR k ← 1 TO n 
      
      FOR i ← 1 TO n
          IF i = k
              CONTINUE
          
          FOR j ← 1 TO n
              IF j = k OR j = i
                  CONTINUE

              d[i][j] ← MIN(d[i][k] + d[k][j], d[i][j])

• d[i][j]: 직전까지 계산된 i에서 j로의 최소 비용
  

경유지 → 출발지 → 목적지로 해야 하는 이유

d[i][j] ← MIN(d[i][k] + d[k][j], d[i][j])

d[i][j] ← MIN(d[i][k] + d[k][j], d[i][j])에서 correctness가 보장되려면
d[i][k]는 i에서 k로 갈 때 1 ~ (k - 1)을 경유지로 고려한 최소비용이어야 한다(d[k][j]도 마찬가지).

즉 d[i][j]를 갱신하는 시점에 이미 d[i][k]와 d[k][j]는 각각 i -> k, k -> j로 가는 최소 비용이어야 한다.

d[i][j]는 점진적으로 최적화된다. 이때 k는 '이번 단계에서 경유지로 사용을 허락할 노드'를 의미한다.
즉 다음과 같이 최적화 된다.
1. k = 1: 기존 경로와 1번 노드만을 경유지로 사용했을 때의 경로 중 더 짧은 경로를 찾는다.
즉 i -> j와 i -> 1 -> j를 비교한다.
2. k = 2: 현재까지의 최단 경로와 2번 까지 경유지로 사용했을 때의 경로 중 더 짧은 경로를 찾는다.
즉 앞에서 비교된 i -> j, i -> 1 -> j와 함께 i -> 2 -> j를 비교하게 된다.

...

n. k = n: 기존 경로와 n번 노드까지 경유지로 사용했을 때의 경로 중 더 짧은 경로를 찾는다.
즉 i -> j, i -> 1 -> j, ..., i -> n -> j 를 비교하게 된다.

즉 k는 알고리즘의 진행 단계를 나타낸다.
k번째 단계가 끝나면 {1, 2, ..., k}노드를 각각 경유지로 사용한 경우의 경로를 비교하고, 그 중 최단 경로가 d[i][j]에 저장된다.

출발지 → 경유지 → 목적지라면

allPairsShortest2(d[1..n][1..n]):
  FOR i ← 1 TO n 
      
      FOR k ← 1 TO n
          IF i = k
              CONTINUE
          
          FOR j ← 1 TO n
              IF j = k OR j = i
                  CONTINUE

              d[i][j] ← MIN(d[i][k] + d[k][j], d[i][j])

이 경우 d[i][j]를 갱신하는 시점에, i에서 k로 가는 최단 경로는 고려되지 않은 상태에서 비교하게 된다.
즉 부분 경로(경유지를 거치는 경우의 경로)의 최단 경로가 계산되지 않은 상태에서 비교하게 되기 때문에 correctness가 보장되지 않는다.

그래서 경유지 → 출발지 → 목적지와 경유지 → 목적지 → 출발지는 되지만 그 외의 경우는 불가능하다.

Implementation(양의 가중치만 있을 때)

distance = new int[N][N];
for(int i = 0; i < N; ++i) {
    for(int j = 0; j < N; ++j) {
        distance[i][j] = sc.nextInt();
        //자기자신으로의 인접 정보가 아니고 인접해있지 않다면 INF로 채우기
        if(i != j && distance[i][j] == 0) { //Sentinel
            distance[i][j] = INF;
        }
    }
}

// 출발지-->경유지-->목적지로 3중 루프 돌리면 오답
// 경유지-->출발지-->목적지로 3중 루프 돌려야 정답
for(int k = 0; k < N; ++k) {
    for(int i = 0; i < N; ++i) {
        if(i == k) continue; // 출발지와 경유지가 같다면 다음 출발지
        for(int j = 0; j < N; ++j) {
            if(i == j || k == j) continue; // 경유지와 목적지가 같거나 출발지가 곧 목적지라면 패스
            if(distance[i][j] > distance[i][k] + distance[k][j]) {
                distance[i][j] = distance[i][k] + distance[k][j];
            }
        }
    }
}

Example: BOJ 2458

import java.io.*;
import java.util.*;

public class Main {
    static boolean[][] isAdjacent;
    static int n, m;

    public static void main(String[] args)
    throws Exception {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in)); 
        StringTokenizer st = new StringTokenizer(br.readLine(), " ");
        n = Integer.parseInt(st.nextToken());
        m = Integer.parseInt(st.nextToken());
        isAdjacent = new boolean[n][n];

        for(int idx = 0; idx < m; ++idx) {
            st = new StringTokenizer(br.readLine(), " ");
            int i = Integer.parseInt(st.nextToken());
            int j = Integer.parseInt(st.nextToken());
            isAdjacent[i - 1][j - 1] = true;
        }

        for(int k = 0; k < n; ++k) { //경유지
            for(int i = 0; i < n; ++i) { //출발지
                //경유지와 출발지가 같은 경우
                if(i == k) continue; 

                for(int j = 0; j < n; ++j) { //목적지
                    //출발지와 목적지 또는 경유지와 목적지가 같은 경우
                    if(i == j || k == j) continue;

                    if(isAdjacent[i][k] && isAdjacent[k][j]) {
                        isAdjacent[i][j] = true;
                    }
                }
            }
        }

        //count = 각 i에 대해 노드 i와 연결된 노드의 수
        int answer = 0;
        for(int i = 0; i < n; i++) {
            int count = 0;
            for(int j = 0; j < n; j++) {
                if(isAdjacent[i][j] || isAdjacent[j][i]) {
                    ++count;
                }
            }
            if(count == n - 1) {
                ++answer;
            }
        }

        System.out.print(answer);
        br.close();
    }

}

Example: BOJ 1389

import sys

input = sys.__stdin__.readline

def main():
    n, m = map(int, input().rstrip().split())
    INF = n**2
    dist = [[0 if i == j else INF for j in range(n)] for i in range(n)]

    for _ in range(m):
        a, b = map(int, input().rstrip().split())
        dist[a - 1][b - 1] = 1
        dist[b - 1][a - 1] = 1

    # Floyd - Warshall
    for k in range(n):
        for i in range(n):
            if i == k:
                continue
            for j in range(n):
                if i == j or j == k:
                    continue

                dist[i][j] = min(dist[i][j], dist[i][k] + dist[j][k])

    # 케빈 베이컨 수 계산
    answer = n # Sentinel
    min_cb = n**2 # Sentinel
    for i in range(n):
        cb = 0
        for j in range(n):
            cb += dist[i][j]
        if min_cb > cb:
            min_cb = cb
            answer = i

    print(answer + 1)


main()