II-13 Dijkstra와 Bellman-Ford의 가중치 전제 — 완전 초보자 Masterclass
먼저 이 문제의 정체부터
두 알고리즘의 차이는 graph가 DAG인지보다 negative edge를 다루는 방식에 있습니다. Dijkstra는 확정한 거리가 나중에 줄지 않는다는 greedy 전제가 필요합니다.
Dijkstra는 되돌아가면 더 싸지는 할인 쿠폰이 없다고 믿고 결제를 확정하는 방식입니다.
이 문항의 풀이 목표는 정답 label 암기가 아니라 다음 절차를 재현하는 것입니다. \(\text{Dijkstra}\to w\ge 0, \text{Bellman}-\text{Ford}\to \text{negative} \text{edge} \text{OK}/\text{negative} \text{cycle} \text{detect}\)Dijkstra→w≥0, Bellman-Ford→negative edge OK/negative cycle detect를 먼저 씁니다.
복기 시험지는 공식 답안지가 아니므로 문언과 selection rule이 충돌하면 그 사실을 표시하고 현재 강의 자료로 각 보기를 독립 검증합니다.
0. 필요한 개념을 처음부터 배우기
개념 1 · 문제의 정체를 생활 언어로
두 알고리즘의 차이는 graph가 DAG인지보다 negative edge를 다루는 방식에 있습니다. Dijkstra는 확정한 거리가 나중에 줄지 않는다는 greedy 전제가 필요합니다.
이 문항에서 가장 먼저 붙잡을 문장은 '다익스트라(Dijkstra)는 모든 간선 가중치가 0 이상이어야 한다.'입니다. 용어를 외우기 전에 이 문장이 어떤 상황을 말하는지 작은 예를 만들어 확인합니다.
이 절에서 꼭 기억할 것
- 다익스트라(Dijkstra)는 모든 간선 가중치가 0 이상이어야 한다.
- \(\text{Dijkstra}\to w\ge 0, \text{Bellman}-\text{Ford}\to \text{negative} \text{edge} \text{OK}/\text{negative} \text{cycle} \text{detect}\)
Dijkstra→w≥0, Bellman-Ford→negative edge OK/negative cycle detect를 먼저 씁니다.
개념 2 · 반드시 알아야 하는 네 개의 뼈대
첫째, 다익스트라(Dijkstra)는 모든 간선 가중치가 0 이상이어야 한다. 둘째, Dijkstra는 cycle이 있는 graph에서도 작동할 수 있다.
셋째, Bellman-Ford는 negative edges를 허용한다. 넷째, reachable negative cycle이 있으면 finite shortest distance가 없을 수 있고 이를 검출한다. 이 네 문장을 서로 섞지 않고 별도 체크박스로 기억해야 합니다.
이 절에서 꼭 기억할 것
- 다익스트라(Dijkstra)는 모든 간선 가중치가 0 이상이어야 한다.
- Dijkstra는 cycle이 있는 graph에서도 작동할 수 있다.
- Bellman-Ford는 negative edges를 허용한다.
- reachable negative cycle이 있으면 finite shortest distance가 없을 수 있고 이를 검출한다.
개념 3 · 강의 정의를 초보자 언어로 해체
최단 경로 문제는 출발점 s에서 각 정점까지의 현재 최선 후보 거리 dist를 계속 줄여 가는 문제다. Dijkstra는 '가장 가까워 보이는 정점은 이제 확정해도 된다'는 빠른 그리디(greedy) 판단을 사용하지만, 이는 뒤에서 음수 간선이 나타나 dist를 더 줄일 수 없다는 비음수 조건에 의존한다. Bellman-Ford는 그리디하게 확정하지 않고 모든 간선을 여러 번 훑으므로 음수 간선도 처리한다.
단일 출발점 최단 경로(SSSP, single-source shortest paths)는 출발점 s에서 도달 가능한 모든 정점 v까지의 shortest(s,v)를 구하는 문제다. 완화(Relaxation, Lockerung)는 간선 (u,v)에 대해 \(v.\text{dist} > u.\text{dist} + w(u,v)\)v.dist > u.dist + w(u,v)이면 v.dist := u.dist + w(u,v), v.pred := u로 갱신하는 연산이다. Dijkstra 알고리즘은 Q에서 dist가 가장 작은 정점 u를 꺼내고(EXTRACT-MIN) u에서 나가는 간선을 완화한다. Bellman-Ford 알고리즘은 |V|-1회 동안 모든 간선을 완화하고, 추가 검사에서도 완화 가능한 간선이 있으면 출발점에서 도달 가능한 음수 사이클을 보고한다.
수식으로 정확히 쓰기
핵심 규칙Dijkstra는 \(w(u,v) \ge 0\)w(u,v) ≥ 0을 요구하며, 강의의 Fibonacci 힙 구현에서 실행시간은 \(\Theta(|V| \log |V| + |E|)\)Θ(|V| log |V| + |E|)이다. Bellman-Ford는 \(\Theta(|V|\cdot |E|)\)Θ(|V|·|E|)이며 음수 간선을 허용한다. 도달 가능한 음수 사이클이 있으면 유한한 최단 경로 답이 없다.
이 절에서 꼭 기억할 것
- 그래프 방향이 중요하다. 방향 간선 (u,v)과 무방향 간선 {u,v}는 다르게 처리한다.
- 강의의 Dijkstra에서는 모든 간선이 \(w(u,v) \ge 0\)
w(u,v) ≥ 0을 만족해야 하며 0도 포함된다. - Bellman-Ford는 음수 간선을 허용하지만, 도달 가능한 음수 사이클이 있으면 유한한 최단 거리가 정의되지 않는다.
개념 4 · 성립 조건·불변식·경계 사례
Dijkstra의 핵심 불변식은 비음수 가중치 아래에서 u가 Q에서 추출될 때 \(u.\text{dist} = \text{shortest}(s,u)\)u.dist = shortest(s,u)가 된다는 것이다. Bellman-Ford는 충분히 반복하면 간선이 최대 |V|-1개인 모든 최단 단순 경로의 정보가 완화를 통해 전파된다. 출발점에서 도달 가능한 사이클의 총가중치가 음수이면 반복할수록 경로 비용을 끝없이 줄일 수 있으므로, 영향을 받는 정점에는 유한한 최단 경로 값이 없다.
가중치 0인 간선은 음이 아니므로 Dijkstra에서 허용된다. 양수 사이클이나 가중치 0인 사이클이 있다고 Dijkstra가 중단하지는 않으며 Q가 빌 때까지 정점을 처리한다. 도달 가능한 음수 사이클이 없는 음수 간선은 Bellman-Ford가 처리할 수 있다. 반면 무방향 그래프의 음수 간선은 양방향 표현에서 음수 2-사이클을 만들므로 Bellman-Ford는 음수 사이클을 검출하고 Dijkstra는 적용할 수 없다. 음수 가중치가 있는 DAG에는 위상 순서 기반 SSSP도 있지만 Dijkstra 자체가 DAG에만 제한되는 것은 아니다.
이 절에서 꼭 기억할 것
- 전제조건을 생략하지 않는다.
- 존재 명제와 모든 경우 명제를 구분한다.
- 강한 단어는 작은 반례로 우선 검사한다.
개념 5 · 실행시간과 비용을 읽는 법
강의의 Fibonacci 힙 기반 Dijkstra 실행시간은 \(\Theta(|V| \log |V| + |E|)\)Θ(|V| log |V| + |E|)이다. 구현에 따라 이진 힙은 흔히 \(O((|V|+|E|) \log |V|)\)O((|V|+|E|) log |V|), 행렬·배열 방식은 \(O(|V|^2)\)O(|V|²)이 될 수 있다. Bellman-Ford의 실행시간은 \(\Theta(|V|\cdot |E|)\)Θ(|V|·|E|)이다. 두 알고리즘 모두 정점마다 dist와 pred를 저장하므로 그래프 표현 외에 \(O(|V|)\)O(|V|)의 추가 정점 상태 메모리를 사용한다.
O는 upper bound이고 Θ는 tight bound입니다. 자료구조 연산 비용은 ADT 이름만이 아니라 구현과 유지하는 보조 정보에 따라 달라질 수 있습니다.
이 절에서 꼭 기억할 것
- O와 Θ를 같은 뜻으로 읽지 않는다.
- 구현 의존성을 확인한다.
- 필요 없는 runtime 주장도 억지로 만들지 않는다.
개념 6 · 정확히 두 개 선택(exactly two) 판정법
선택지를 서로 비교해 '가장 그럴듯한 두 개'를 고르지 않습니다. A부터 D까지 각각 독립적인 참·거짓 명제로 바꾸고 근거 또는 반례를 붙인 뒤 참의 개수를 셉니다.
현재 복기 데이터에서 판정된 정답 표시는 A, D입니다. 정답 수와 섹션 규칙이 충돌하는 문항은 억지로 두 개를 만들지 않고 복기 문언 누락 가능성을 명시합니다.
수식으로 정확히 쓰기
핵심 규칙선택 규칙: 정확히 두 개 선택\((\text{exactly}_{\text{two}})\)(exactly(two))
핵심 규칙검증된 선택지: A, D
이 절에서 꼭 기억할 것
- Dijkstra의 제한은 DAG가 아니라 음수가 아닌 가중치이며, Bellman-Ford는 음수 간선을 허용하지만 음수 순환은 별도로 처리해야 합니다.
- Dijkstra는 \(w\ge 0, \text{Bellman}-\text{Ford}\)
w≥0, Bellman-Ford는 음수 간선을 허용하고 도달 가능한 음수 순환을 검출한다고 정리합니다. DAG 전용이라는 문장은 Dijkstra가 아니라 위상 순서 SSSP에 해당합니다.
1. 시험장에서 따라 할 풀이 순서
선택 규칙 = 정확히 두 개 선택\((\text{exactly}_{\text{two}})\)(exactly(two))
Dijkstra와 Bellman-Ford의 가중치 전제
다익스트라(Dijkstra)는 모든 간선 가중치가 0 이상이어야 한다. | Dijkstra는 cycle이 있는 graph에서도 작동할 수 있다. | Bellman-Ford는 negative edges를 허용한다.
선택지 \(A =\)A =참
선택 규칙을 먼저 적는다
이 문항의 규칙은 정확히 두 개 선택\((\text{exactly}_{\text{two}})\)
(exactly(two))입니다. 마지막에 참 개수를 반드시 재검산합니다.핵심 규칙선택 규칙 = 정확히 두 개 선택\((\text{exactly}_{\text{two}})\)
(exactly(two))문장을 쉬운 한국어로 다시 쓴다
Dijkstra와 Bellman-Ford 알고리즘에 대한 다음 설명 중 정확히 두 개를 고르시오.
핵심 규칙Dijkstra와 Bellman-Ford의 가중치 전제
핵심 도구를 종이에 꺼낸다
\(\text{Dijkstra}\to w\ge 0, \text{Bellman}-\text{Ford}\to \text{negative} \text{edge} \text{OK}/\text{negative} \text{cycle} \text{detect}\)
Dijkstra→w≥0, Bellman-Ford→negative edge OK/negative cycle detect를 먼저 씁니다.핵심 규칙다익스트라(Dijkstra)는 모든 간선 가중치가 0 이상이어야 한다. | Dijkstra는 cycle이 있는 graph에서도 작동할 수 있다. | Bellman-Ford는 negative edges를 허용한다.
선택지 A를 독립 판정한다
강의 슬라이드는 Dijkstra 의사코드 바로 옆에 전제(Voraussetzung) \(w(u,v) \ge 0\)
w(u,v) ≥ 0für alle Kanten를 둡니다. 이 조건 덕분에 최소값 추출(EXTRACT-MIN)로 꺼낸 정점의 거리 dist가 나중에 더 작아지지 않는다는 불변식(invariant)을 증명할 수 있습니다.\[선택지 A = 참\]선택지 A = 참선택지 B를 독립 판정한다
Dijkstra의 핵심 전제는 비순환(acyclic)이 아니라 음수가 아닌 간선 가중치입니다. 강의에는 DAG용 단일 출발점 최단 경로(SSSP) 알고리즘이 따로 나오며 Dijkstra와 별개입니다. 가중치가 모두 음수가 아니면 순환이 있어도 Dijkstra를 사용할 수 있습니다.
\[선택지 B = 거짓\]선택지 B = 거짓선택지 C를 독립 판정한다
이는 Dijkstra의 전제를 Bellman-Ford에 잘못 옮긴 문장입니다. 강의의 SSSP 개요는 Bellman-Ford를 일반적으로 동작하는 알고리즘으로 제시하고, 의사코드에는 음수 순환 검출(negative-cycle detection)도 포함합니다. 연습문제에서도 음수 간선이 있는 그래프에 Bellman-Ford를 적용합니다.
\[선택지 C = 거짓\]선택지 C = 거짓선택지 D를 독립 판정한다
의도된 대비는 'Bellman-Ford는 음수 간선(negative edge)을 허용한다'는 것입니다. 다만 '동작한다(funktioniert)'를 언제나 유한한 최단 경로를 반환한다는 뜻으로 읽으면, 도달 가능한 음수 순환이 있을 때 최단 거리가 정의되지 않아 모호합니다. 강의 알고리즘은 이 경우 false를 반환해 음수 순환을 검출하는 것까지 포함합니다.
\[선택지 D = 참\]선택지 D = 참정답 수와 애매성을 재검산한다
참으로 판정된 선택지는 A, D입니다. 복기 섹션 규칙과 수가 다르면 원문 누락 가능성을 기록하고 거짓을 참으로 조작하지 않습니다.
\[검증된 정답 = A, D\]검증된 정답 = A, D
2. 이 문제를 실제로 끝까지 풀기
두 알고리즘의 차이는 graph가 DAG인지보다 negative edge를 다루는 방식에 있습니다. Dijkstra는 확정한 거리가 나중에 줄지 않는다는 greedy 전제가 필요합니다.
풀이를 시작할 때 다음 네 사실을 먼저 적습니다. (1) 다익스트라(Dijkstra)는 모든 간선 가중치가 0 이상이어야 한다. (2) Dijkstra는 cycle이 있는 graph에서도 작동할 수 있다. (3) Bellman-Ford는 negative edges를 허용한다. (4) reachable negative cycle이 있으면 finite shortest distance가 없을 수 있고 이를 검출한다.
선택지 A는 참입니다. 강의 슬라이드는 Dijkstra 의사코드 바로 옆에 전제(Voraussetzung) \(w(u,v) \ge 0\)w(u,v) ≥ 0 für alle Kanten를 둡니다. 이 조건 덕분에 최소값 추출(EXTRACT-MIN)로 꺼낸 정점의 거리 dist가 나중에 더 작아지지 않는다는 불변식(invariant)을 증명할 수 있습니다.
선택지 B는 거짓입니다. Dijkstra의 핵심 전제는 비순환(acyclic)이 아니라 음수가 아닌 간선 가중치입니다. 강의에는 DAG용 단일 출발점 최단 경로(SSSP) 알고리즘이 따로 나오며 Dijkstra와 별개입니다. 가중치가 모두 음수가 아니면 순환이 있어도 Dijkstra를 사용할 수 있습니다. 가장 작은 확인 예는 \(s\to a\)s→a의 가중치가 \(1, a\to s\)1, a→s가 \(1, s\to t\)1, s→t가 2인 방향 순환에서는 모든 가중치가 음수가 아니므로 순환이 있어도 Dijkstra가 정상 동작합니다.
선택지 C는 거짓입니다. 이는 Dijkstra의 전제를 Bellman-Ford에 잘못 옮긴 문장입니다. 강의의 SSSP 개요는 Bellman-Ford를 일반적으로 동작하는 알고리즘으로 제시하고, 의사코드에는 음수 순환 검출(negative-cycle detection)도 포함합니다. 연습문제에서도 음수 간선이 있는 그래프에 Bellman-Ford를 적용합니다. 가장 작은 확인 예는 \(s\to a\)s→a의 가중치가 -2이고 순환이 없다면 Bellman-Ford는 이 간선을 완화해 \(\text{dist}(a)=-2\)dist(a)=-2를 반환합니다.
선택지 D는 참입니다. 의도된 대비는 'Bellman-Ford는 음수 간선(negative edge)을 허용한다'는 것입니다. 다만 '동작한다(funktioniert)'를 언제나 유한한 최단 경로를 반환한다는 뜻으로 읽으면, 도달 가능한 음수 순환이 있을 때 최단 거리가 정의되지 않아 모호합니다. 강의 알고리즘은 이 경우 false를 반환해 음수 순환을 검출하는 것까지 포함합니다.
따라서 현재 문언에서 참으로 검증된 선택지는 A, D입니다. 선택지는 서로 상대평가하지 않고 각 문장을 정의·전제·반례로 독립 검증했습니다.
시험장에서 쓸 압축 절차는 다음과 같습니다. \(\text{Dijkstra}\to w\ge 0, \text{Bellman}-\text{Ford}\to \text{negative} \text{edge} \text{OK}/\text{negative} \text{cycle} \text{detect}\)Dijkstra→w≥0, Bellman-Ford→negative edge OK/negative cycle detect를 먼저 씁니다. 시간이 부족해도 '항상(always)', '오직(only)', '모든(every)' 같은 강한 단어와 전제조건, O와 Θ를 먼저 확인하면 대표 함정을 피할 수 있습니다.
3. 선택지 A–D를 한 줄도 건너뛰지 않고 판정하기
-
A참 — 정답 후보
강의 슬라이드는 Dijkstra 의사코드 바로 옆에 전제(Voraussetzung) \(w(u,v) \ge 0\)
w(u,v) ≥ 0für alle Kanten를 둡니다. 이 조건 덕분에 최소값 추출(EXTRACT-MIN)로 꺼낸 정점의 거리 dist가 나중에 더 작아지지 않는다는 불변식(invariant)을 증명할 수 있습니다.빠른 확인법: Dijkstra 알고리즘은 음수가 아닌 간선 가중치(nonnegative edge weights)에서만 동작한다.
-
B거짓
Dijkstra의 핵심 전제는 비순환(acyclic)이 아니라 음수가 아닌 간선 가중치입니다. 강의에는 DAG용 단일 출발점 최단 경로(SSSP) 알고리즘이 따로 나오며 Dijkstra와 별개입니다. 가중치가 모두 음수가 아니면 순환이 있어도 Dijkstra를 사용할 수 있습니다.
빠른 확인법: \(s\to a\)
s→a의 가중치가 \(1, a\to s\)1, a→s가 \(1, s\to t\)1, s→t가 2인 방향 순환에서는 모든 가중치가 음수가 아니므로 순환이 있어도 Dijkstra가 정상 동작합니다. -
C거짓
이는 Dijkstra의 전제를 Bellman-Ford에 잘못 옮긴 문장입니다. 강의의 SSSP 개요는 Bellman-Ford를 일반적으로 동작하는 알고리즘으로 제시하고, 의사코드에는 음수 순환 검출(negative-cycle detection)도 포함합니다. 연습문제에서도 음수 간선이 있는 그래프에 Bellman-Ford를 적용합니다.
빠른 확인법: \(s\to a\)
s→a의 가중치가 -2이고 순환이 없다면 Bellman-Ford는 이 간선을 완화해 \(\text{dist}(a)=-2\)dist(a)=-2를 반환합니다. -
D참 — 정답 후보
의도된 대비는 'Bellman-Ford는 음수 간선(negative edge)을 허용한다'는 것입니다. 다만 '동작한다(funktioniert)'를 언제나 유한한 최단 경로를 반환한다는 뜻으로 읽으면, 도달 가능한 음수 순환이 있을 때 최단 거리가 정의되지 않아 모호합니다. 강의 알고리즘은 이 경우 false를 반환해 음수 순환을 검출하는 것까지 포함합니다.
빠른 확인법: Bellman-Ford 알고리즘은 모든 간선 가중치가 음수인 그래프에서도 동작한다.
4. 초보자가 가장 자주 틀리는 이유
- Dijkstra의 제한은 DAG가 아니라 음수가 아닌 가중치이며, Bellman-Ford는 음수 간선을 허용하지만 음수 순환은 별도로 처리해야 합니다.
- exactly-two라는 이유만으로 근거 없이 두 선택지를 맞다고 만든다.
- 선택지의 절반만 맞는데 결합 문장 전체를 참으로 판정한다.
- always, only, every 같은 강한 단어를 놓친다.
- 정의와 구현, 전제조건과 결론, upper bound와 tight bound를 섞는다.
- 작은 예 하나로 거짓은 깰 수 있지만 참인 보편 명제를 증명했다고 착각한다.
- 복기 시험지가 공식 원문·공식 답안이라는 전제로 애매성을 숨긴다.
- 용어를 암기한 소리만 따라가고 실제 상태나 한 단계 실행을 그리지 않는다.
5. 시험 답안 템플릿
\(\text{Dijkstra}\to w\ge 0, \text{Bellman}-\text{Ford}\to \text{negative} \text{edge} \text{OK}/\text{negative} \text{cycle} \text{detect}\)Dijkstra→w≥0, Bellman-Ford→negative edge OK/negative cycle detect를 먼저 씁니다. 각 선택지를 정의와 전제에 따라 독립 판정하면 참인 label은 A, D이다. 핵심 근거: 다익스트라(Dijkstra)는 모든 간선 가중치가 0 이상이어야 한다. Dijkstra는 cycle이 있는 graph에서도 작동할 수 있다. Bellman-Ford는 negative edges를 허용한다. reachable negative cycle이 있으면 finite shortest distance가 없을 수 있고 이를 검출한다.
6. 스스로 이해했는지 확인
II-13의 주제를 한 문장으로 설명하면?
정답: 두 알고리즘의 차이는 graph가 DAG인지보다 negative edge를 다루는 방식에 있습니다. Dijkstra는 확정한 거리가 나중에 줄지 않는다는 greedy 전제가 필요합니다.
이 문제에서 가장 먼저 꺼낼 판정법은?
정답: \(\text{Dijkstra}\to w\ge 0, \text{Bellman}-\text{Ford}\to \text{negative} \text{edge} \text{OK}/\text{negative} \text{cycle} \text{detect}\)Dijkstra→w≥0, Bellman-Ford→negative edge OK/negative cycle detect를 먼저 씁니다.
핵심 사실 네 가지 중 첫 번째는?
정답: 다익스트라(Dijkstra)는 모든 간선 가중치가 0 이상이어야 한다.
핵심 사실 네 가지 중 두 번째는?
정답: Dijkstra는 cycle이 있는 graph에서도 작동할 수 있다.
가장 위험한 함정은?
정답: Dijkstra의 제한은 DAG가 아니라 음수가 아닌 가중치이며, Bellman-Ford는 음수 간선을 허용하지만 음수 순환은 별도로 처리해야 합니다.
정답 label은?
정답: A, D
Dijkstra의 정확성 불변식(invariant)을 한 문장으로 말하라.
정답: 모든 간선 가중치가 음이 아닐 때 Q에서 EXTRACT-MIN된 정점 u는 그 순간 \(u.\text{dist} = \text{shortest}(s,u)\)u.dist = shortest(s,u)가 되어 최종 확정된다.
Bellman-Ford가 |V|-1회 반복하는 이유는 무엇인가?
정답: 도달 가능한 음수 사이클이 없으면 최단 단순 경로는 정점을 반복할 필요가 없어 간선 수가 최대 |V|-1개이고, 각 반복이 경로의 다음 간선 효과를 전파할 수 있기 때문이다.
근거 자료
AuD Gedächtnisprotokoll SoSe 2025.md· Multiple Choice II-13
복기된 문언과 선택지; 공식 답안지가 아님AuD Gedächtnisprotokoll SoSe 2025.md· MC section lines 136-146
정확히 두 개 선택 규칙을 포함한 2025년 여름학기 II-13·II-14 복기 문구.Vorlesung\06GraphAlgorithms.pdf· pp. 127-130
최단 부분 경로 성질, 단일 출발점 최단 경로 알고리즘 개요, 완화 규칙, Bellman-Ford 실행 시간과 음수 순환 검사.Vorlesung\06GraphAlgorithms.pdf· pp. 130-141
Bellman-Ford는 모든 간선을 |V|-1회 완화한 뒤 도달 가능한 음수 순환을 감지하며, 실행 시간은 \(\Theta(|V||E|)\)Θ(|V||E|)입니다.Vorlesung\06GraphAlgorithms__moodle_2026-06-16.pdf· pp. 152-174
현재 Moodle 자료는 Dijkstra의 전제 \(w(u,v) \ge 0, \text{Fibonacci}\)w(u,v) ≥ 0, Fibonacci힙을 사용할 때의 실행 시간 \(\Theta(|V| \log |V|+|E|)\)Θ(|V| log |V|+|E|), 정확성 불변식, 음수 간선 반례와 무방향 그래프 관례를 제시합니다.