최소 신장 트리와 최단 경로

최소 신장 트리와 최단 경로는 같은 그래프를 보지만 정답의 의미가 다릅니다

시험에서 가중 그래프(weighted graph, gewichteter Graph)가 나오면 많은 학생이 바로 Dijkstra, Kruskal, Prim 중 하나를 떠올립니다. 그러나 먼저 물어야 할 질문은 알고리즘 이름이 아니라 목적함수입니다. 최소 신장 트리(MST, minimaler Spannbaum)는 출발점 없이 모든 정점(vertex, Knoten)을 연결하는 트리의 전체 간선 가중치(Gewicht)를 최소화합니다. 최단 경로(shortest path, kürzester Weg)는 출발점 s에서 어떤 정점 v까지의 경로 가중치를 최소화합니다. 따라서 MST는 네트워크 전체 공사비 문제이고, 최단 경로는 한 출발점에서의 내비게이션 문제입니다.

이 차이는 단순한 말장난이 아닙니다. MST 안에서 두 정점을 잇는 경로가 원래 그래프의 최단 경로일 필요는 없습니다. 반대로 출발점에서 각 정점으로 가는 최단 경로 트리가 전체 간선 가중치가 최소인 신장 트리일 필요도 없습니다. AUD 시험의 객관식 함정은 이 둘의 용어를 일부러 비슷하게 놓습니다. key[v], dist[v], pred[v], set(v)가 모두 비슷해 보이지만 의미는 서로 다릅니다. 이 페이지의 목표는 네 알고리즘 이름을 외우는 것이 아니라, 문제 문장을 보고 어떤 최적화 문제인지 즉시 분리하고 중간표를 실수 없이 채우는 것입니다.

선수개념과 어휘 지도

아래 단어를 독일어/영어와 함께 말할 수 있으면 그래프 알고리즘 답안의 절반은 안정됩니다.

기호를 문제 유형별로 고정하기

비슷해 보이는 표기들을 한 줄 의미로 분리해 두면 Prim과 Dijkstra를 섞지 않습니다.

1. MST: 전체 연결망의 총비용을 최소화한다

강의 06의 82~84쪽 정의를 한국어로 풀면 이렇습니다. 입력은 연결된 무방향 가중 그래프 \(G=(V,E)\)G=(V,E)와 가중치 함수 \(w:E\to\mathbb{R}\)w:E→ℝ입니다. 부분 그래프 \(T=(V,E_T)\)T=(V,Eₜ)가 신장 트리가 되려면 모든 정점을 포함하고, 연결되어 있으며, 순환이 없어야 합니다. 그중 \(w(T)=\sum_{\{u,v\}\in E_T}w(u,v)\)w(T)=Σ{u,v}∈Eₜ w(u,v)가 모든 신장 트리 중 최소인 것이 최소 신장 트리(MST, minimaler Spannbaum)입니다.

여기서 출발점이라는 말이 나오지 않는다는 점이 중요합니다. MST는 어느 한 정점에서 출발하는 문제가 아닙니다. 예를 들어 회사 지점 전체를 케이블로 연결해야 한다면, 한 지점에서 다른 지점까지의 개별 이동 경로가 조금 길어져도 전체 설치비가 최소이면 좋은 해입니다. 그래서 MST의 간선 집합은 전체 네트워크 설계이고, 최단 경로의 선행자 트리는 출발점 기준 경로 지도입니다.

트리의 기본 성질도 시험에서 자주 쓰입니다. \(n=|V|\)n=|V|인 신장 트리는 간선이 정확히 n-1개입니다. Kruskal 표를 채울 때 간선 n-1개가 선택되면 신장 트리가 완성됩니다. 선택한 간선이 이미 같은 연결 성분 안의 두 정점을 잇는다면 새 연결을 만들지 않고 순환만 만들기 때문에 MST 후보에서 제외합니다.

2. 안전한 간선과 절단 속성: MST 탐욕법이 맞는 이유

강의 06의 85~91쪽에서 설명하는 일반 MST 아이디어는 \(A=\text{empty}\)A=empty에서 시작해 A가 신장 트리가 될 때까지 안전한 간선(safe edge)을 하나씩 추가하는 것입니다. 안전한 간선이란 A ∪ {e}가 여전히 어떤 MST의 부분집합이 되게 하는 간선입니다. 즉 지금 고른 간선이 나중에 최적해로 완성될 수 있어야 합니다.

절단 속성(cut property)은 안전한 간선을 찾는 대표 도구입니다. 절단 (S,V-S)가 현재 선택한 간선 집합 A를 존중한다는 것은 A의 어떤 간선도 그 절단을 건너지 않는다는 뜻입니다. 그 절단을 건너는 간선 중 가장 가벼운 간선(light edge)은 A에 대해 안전합니다. 증명 직관은 교환 논증(exchange argument)입니다. 어떤 MST T가 A를 포함한다고 합시다. 우리가 고른 가벼운 간선 {u,v}가 이미 T에 있으면 끝입니다. 없다면 T에서 u에서 v로 가는 경로에는 같은 절단을 건너는 다른 간선 {x,y}가 있습니다. {u,v}가 더 가벼우므로 \(w(u,v) \le w(x,y)\)w(u,v) ≤ w(x,y)입니다. 그러면 T - {x,y} + {u,v}도 신장 트리이며 가중치가 커지지 않습니다. 따라서 새 간선을 포함하는 MST가 존재합니다.

이 증명 직관을 말할 수 있으면 Kruskal과 Prim의 정확성이 한 문장으로 정리됩니다. Kruskal이 고르는 간선도 어떤 연결 성분 절단의 가벼운 간선이고, Prim이 고르는 간선도 현재 트리와 바깥 정점 사이 절단의 가벼운 간선입니다. 탐욕 선택이 단순히 “작아 보여서” 맞는 것이 아니라, 절단 속성 때문에 안전한 것입니다.

3. Kruskal: 간선을 가벼운 순서로 보며 순환을 피합니다

Kruskal(Kruskal-Algorithmus)은 강의 06의 93~106쪽과 Sheet10의 표 문제에서 중요합니다. 절차는 네 줄입니다. 첫째, \(A=\text{empty}\)A=empty입니다. 둘째, 모든 정점을 원소 하나짜리 집합으로 둡니다. 셋째, 간선을 가중치가 작아지지 않는 순서로 정렬합니다. 넷째, 그 순서로 간선 {u,v}를 보면서 \(\text{set}(u) \ne \text{set}(v)\)set(u) != set(v)이면 간선을 추가하고 두 집합을 합칩니다. \(\text{set}(u)=\text{set}(v)\)set(u)==set(v)이면 이미 같은 연결 성분 안에 있으므로 그 간선은 순환을 만들고 건너뜁니다.

Sheet10 유형의 표에서는 Dazu?와 set(a), set(b), ... 열을 함께 갱신합니다. 선택하지 않는 간선을 만났을 때도 집합 열은 직전 상태와 같아야 합니다. 문제 지시가 \(=\)=를 사용하라고 하면 변하지 않은 칸에는 \(=\)=를 넣습니다. 간선 가중치가 같다면 문제에서 준 순서나 표의 순서를 따릅니다. 같은 가중치의 처리 순서에 따라 서로 다른 MST가 나올 수 있지만 결과는 모두 MST입니다. MST가 유일하다고 말하려면 추가 조건이 필요합니다.

강의 06의 106쪽에서 기억할 실행 시간 핵심은 간선 정렬이 지배한다는 점입니다. 효율적인 서로소 집합 자료구조를 쓰면 \(O(|E| \log |E|)\)O(|E| log |E|)이며, 단순 그래프에서는 \(\log |E| = \Theta(\log |V|)\)log |E| = Θ(log |V|)이므로 \(O(|E| \log |V|)\)O(|E| log |V|)로도 씁니다. 시험에서는 우선순위 큐나 서로소 집합 구현이 따로 주어졌는지 확인하세요.

4. Prim: 하나의 연결 트리를 경계 간선으로 확장합니다

Prim(Prim-Algorithmus)은 Kruskal처럼 숲을 만들지 않습니다. 강의 06의 108쪽 이후 의사코드는 루트 r에서 시작해 하나의 연결된 부분 트리를 키웁니다. 모든 정점에 \(\text{key}=\infty\)key=∞, \(\text{pred}=\text{NIL}\)pred=NIL을 두고, 루트에는 먼저 뽑히도록 작은 키를 줍니다. 그 뒤 Q에서 키가 가장 작은 정점 u를 꺼내고, u와 인접한 정점 v가 아직 Q 안에 있으며 \(w(\{u,v\}) < v.\text{key}\)w({u,v}) < v.key이면 v.key와 v.pred를 갱신합니다.

가장 흔한 실수는 key[v]를 출발점에서 v까지의 거리라고 생각하는 것입니다. Prim의 key[v]는 현재 트리에 v를 붙이는 간선 하나의 비용입니다. 예를 들어 루트에서 멀리 떨어진 정점이라도 현재 트리의 어느 정점과 가중치 1인 간선으로 연결되면 키는 1입니다. Dijkstra는 출발점에서 누적한 거리를 봅니다. 이 차이가 객관식에서 자주 출제됩니다.

Prim의 정확성도 절단 속성으로 증명합니다. 현재 트리의 정점 집합과 아직 바깥에 있는 정점 집합이 절단을 만들고, key가 가장 작은 정점을 뽑는 것은 그 절단을 건너는 가벼운 간선을 선택하는 것입니다. 따라서 안전한 간선입니다. Prim은 MST 알고리즘이므로 기본 전제는 연결된 무방향 그래프입니다.

5. 최단 경로: dist는 현재까지 발견한 최적 상한입니다

최단 경로 알고리즘의 중심은 dist[v] 또는 v.d입니다. 이것은 지금까지 알고 있는 출발점 s에서 v까지의 최적 상한입니다. 처음에는 \(s.d=0\)s.d=0, 나머지는 ∞입니다. 어떤 간선 (u,v)를 통해 u.d + w(u,v)가 현재 v.d보다 작으면 더 좋은 경로를 찾은 것이므로 v.d와 v.pred를 바꿉니다. 이것이 완화(Relaxation)입니다.

완화는 “간선을 선택한다”와 다릅니다. MST에서는 간선을 트리에 넣을지 결정합니다. 최단 경로에서는 간선을 보고 거리 추정값을 낮출 수 있는지만 봅니다. pred[v]는 현재 최적 경로에서 v 바로 앞 정점을 가리키며, 모든 완화가 끝난 뒤 선행자 포인터가 최단 경로 트리 또는 숲을 이룹니다. 도달할 수 없는 정점은 \(\text{dist}=\infty\)dist=∞, \(\text{pred}=\text{NIL}\)pred=NIL로 남습니다.

BFS도 가중치가 없는 그래프에서 최단 경로를 구한다는 점을 기억하세요. 강의 06의 앞부분은 BFS를 dist와 pred로 설명합니다. 가중 최단 경로에서는 간선 수가 아니라 가중치 합을 보므로 Dijkstra나 Bellman-Ford가 등장합니다.

6. Dijkstra: 최소 거리 추출값이 최종값이 되려면 음수가 아닌 가중치가 필요합니다

Dijkstra(Dijkstra-Algorithmus)는 source s에서 시작합니다. initSSSP 뒤 모든 vertex를 priority queue Q에 넣고, 매번 dist가 가장 작은 vertex u를 extract합니다. 그 순간 \(u.\text{dist} = \text{shortest}(s,u)\)u.dist = shortest(s,u)라고 확정(finalize)하고, u의 outgoing edge를 relax합니다. Lecture 06 pages 161-165의 correctness proof는 이 finality invariant를 증명합니다.

왜 nonnegative weight가 필요할까요? 아직 queue 밖에 남아 있는 vertex를 거쳐 나중에 돌아오는 path가 현재 뽑힌 u보다 갑자기 더 싸질 수 없어야 하기 때문입니다. 모든 edge가 0 이상이면, 이미 가장 작은 tentative distance를 가진 u를 뽑은 뒤에 어떤 미처리 vertex를 경유해도 path weight가 줄어드는 반전이 생기지 않습니다. Lecture 06 pages 166-172는 negative edge counterexample을 보여 줍니다. 처음에는 direct path가 좋아 보이지만, 나중에 negative edge를 포함한 우회 path가 더 싸져서 이미 확정한 vertex를 고쳐야 하는 상황이 생깁니다.

MC에서 두 문장을 분리해야 합니다. Dijkstra는 DAG에서만 동작하는 알고리즘이 아닙니다. cycle이 있어도 edge weight가 nonnegative이면 됩니다. 그리고 0-weight edge는 허용됩니다. 조건은 \(w(e) \ge 0\)w(e) ≥ 0이지 \(w(e) > 0\)w(e) > 0가 아닙니다. 단, extracted order가 tie일 때는 여러 올바른 predecessor tree가 가능할 수 있습니다.

7. Bellman-Ford: 모든 간선을 반복해서 완화하고 음수 순환을 감지합니다

Bellman-Ford는 Dijkstra보다 느리지만 negative edge를 허용합니다. 핵심 아이디어는 shortest simple path가 negative cycle 없이 최대 |V|-1개의 edge만 가질 수 있다는 사실입니다. 그래서 모든 edge를 한 번 relax하면 edge 1개짜리 shortest 후보가 반영되고, 두 번 반복하면 edge 2개짜리 후보가 반영되는 식으로 생각할 수 있습니다. |V|-1 rounds 뒤에는 모든 simple shortest path 후보가 반영되어야 합니다.

그 뒤에도 어떤 edge (u,v)가 \(v.d > u.d + w(u,v)\)v.d > u.d + w(u,v)를 만족한다면, 더 짧은 walk가 계속 생기는 것입니다. 이는 source에서 reachable한 negative cycle이 있음을 의미합니다. 이때는 "최단거리 값"을 유한한 숫자로 반환하면 안 됩니다. cycle을 더 돌수록 weight를 계속 줄일 수 있기 때문입니다.

Undirected graph의 negative edge caveat도 중요합니다. Lecture 06 page 174는 undirected edge를 두 directed arcs로 보는 표현에서 negative undirected edge가 바로 negative cycle을 만든다고 설명합니다. 따라서 undirected graph에서 negative weight가 보이면 Bellman-Ford를 무조건 편하게 쓰면 된다고 말하지 말고, 문제의 graph model과 negative cycle 의미를 확인해야 합니다.

같은 그래프에서 MST와 최단 경로가 다른 간선을 고르는 예

그래프의 정점은 A,B,C,D이고 무방향 간선은 \(\text{AB}=1\)AB=1, \(\text{BC}=1\)BC=1, \(\text{CD}=1\)CD=1, \(\text{AD}=2\)AD=2, \(\text{AC}=3\)AC=3이라고 하겠습니다.

Kruskal 표를 손으로 채우는 방법

Sheet10의 Kruskal table 유형은 알고리즘을 이해했는지와 표를 성실히 갱신하는지를 같이 봅니다. 아래는 간단한 예입니다. Vertices a,b,c,d, edges ab:1, bc:2, ac:3, cd:4, bd:5.

Dijkstra와 Bellman-Ford의 relaxation 감각 비교

Directed graph에서 source는 s이고 edges는 \(s\rightarrow a:2\)s→a:2, \(s\rightarrow b:5\)s→b:5, \(a\rightarrow b:1\)a→b:1, \(b\rightarrow c:2\)b→c:2, \(a\rightarrow c:6\)a→c:6라고 합시다. 모든 weight가 nonnegative이므로 Dijkstra를 쓸 수 있습니다.

Bellman-Ford를 표 없이 말로 추적하기

Bellman-Ford는 표를 모두 그리지 않아도 round의 의미를 말할 수 있어야 합니다. Source s, edges \(s\rightarrow a:4\)s→a:4, \(s\rightarrow b:5\)s→b:5, \(a\rightarrow b:-2\)a→b:-2, \(b\rightarrow c:3\)b→c:3, \(a\rightarrow c:6\)a→c:6라고 합시다. Negative edge는 있지만 negative cycle은 없습니다.

문제 문장에서 알고리즘을 고르는 절차

실전에서는 그림이 복잡해서 알고리즘 이름부터 떠오르기 쉽습니다. 아래 순서로 읽으면 문제 유형을 잘못 고를 가능성이 줄어듭니다.

네 알고리즘을 한 표로 비교하기

비슷한 단어를 한 칸씩 분리해서 외우면 MC에서 섞이지 않습니다.

서술형에서 감점되는 답안 패턴

자주 틀리는 생각 바로잡기

선지 판단을 위한 반례 세트

구두시험에서 말할 증명 뼈대

60초·3분·심화 답안 스크립트

손으로 알고리즘을 실행할 때의 답안 틀

그래프 알고리즘 문제는 최종 edge set이나 distance 값만 맞아도 부분점수는 받을 수 있지만, 중간 상태를 요구하는 Sheet10식 문제에서는 표를 채우는 습관이 점수입니다. 아래 틀은 실제 답안지에서 한 줄씩 확인할 순서입니다.

교수가 이어서 물을 수 있는 질문과 답의 방향

구두시험에서는 첫 답이 맞으면 바로 더 깊게 묻습니다. 아래 질문은 답을 외우기보다 방향을 기억하는 용도입니다.

힌트가 붙은 회상 질문

답을 보지 말고 한 문장씩 말해 보세요. 힌트는 막힐 때만 확인합니다.