최단 경로, Dijkstra, Bellman-Ford

완화(relaxation)는 u를 거쳐 v로 가는 비용이 더 작으면 v.dist와 v.pred를 갱신하는 규칙이다. Dijkstra는 모든 간선 가중치가 음이 아닌 값(nonnegative), 즉 \(w(u,v) \ge 0\)w(u,v) ≥ 0일 때 최솟값 추출(extract-min)로 꺼낸 정점의 dist가 최종값이라는 불변식을 사용한다. 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|)이며 음수 간선을 허용한다. 도달 가능한 음수 사이클이 있으면 유한한 최단 경로 답이 없다.

문장에 nur, DAG, Zyklus, Kantengewicht 0, O와 Θ의 차이, |E| 항 누락, 음수 간선과 음수 사이클의 혼동이 나오면 바로 전제부터 확인한다.

II

2

섹션 II는 A~D 가운데 정확히 두 개가 옳은 형식\((\text{exactly}_{\text{two}})\)(exactly(two))이다.

• II-13
• II-14

정답 글자를 외우는 대신 간선 가중치 전제, 음수 사이클, 그래프 방향, 실행시간 구현 가정을 보고 각 선택지를 독립적으로 참·거짓 판정한다.

기억 복원 자료(Gedächtnisprotokoll)는 재구성한 시험 문구이며 공식 정답지가 아니다. 아래 판정은 2026년 여름학기 강의와 연습 자료를 이용해 독립적으로 검토했다.

최단 경로 문제는 출발점 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회 동안 모든 간선을 완화하고, 추가 검사에서도 완화 가능한 간선이 있으면 출발점에서 도달 가능한 음수 사이클을 보고한다.

• 그래프 방향이 중요하다. 방향 간선 (u,v)과 무방향 간선 {u,v}는 다르게 처리한다.
• 강의의 Dijkstra에서는 모든 간선이 \(w(u,v) \ge 0\)w(u,v) ≥ 0을 만족해야 하며 0도 포함된다.
• Bellman-Ford는 음수 간선을 허용하지만, 도달 가능한 음수 사이클이 있으면 유한한 최단 거리가 정의되지 않는다.

Dijkstra의 핵심 불변식은 비음수 가중치 아래에서 u가 Q에서 추출될 때 \(u.\text{dist} = \text{shortest}(s,u)\)u.dist = shortest(s,u)가 된다는 것이다. Bellman-Ford는 충분히 반복하면 간선이 최대 |V|-1개인 모든 최단 단순 경로의 정보가 완화를 통해 전파된다. 출발점에서 도달 가능한 사이클의 총가중치가 음수이면 반복할수록 경로 비용을 끝없이 줄일 수 있으므로, 영향을 받는 정점에는 유한한 최단 경로 값이 없다.

강의의 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|)의 추가 정점 상태 메모리를 사용한다.

가중치 0인 간선은 음이 아니므로 Dijkstra에서 허용된다. 양수 사이클이나 가중치 0인 사이클이 있다고 Dijkstra가 중단하지는 않으며 Q가 빌 때까지 정점을 처리한다. 도달 가능한 음수 사이클이 없는 음수 간선은 Bellman-Ford가 처리할 수 있다. 반면 무방향 그래프의 음수 간선은 양방향 표현에서 음수 2-사이클을 만들므로 Bellman-Ford는 음수 사이클을 검출하고 Dijkstra는 적용할 수 없다. 음수 가중치가 있는 DAG에는 위상 순서 기반 SSSP도 있지만 Dijkstra 자체가 DAG에만 제한되는 것은 아니다.

• nur
• nicht-negative Kantengewichte
• Directed Acyclic Graphs
• Zyklus
• Kantengewichte dürfen 0 sein
• \(O(|V| \log |V|)\)O(|V| log |V|)
• \(\Theta(|V| \log |V| + |E|)\)Θ(|V| log |V| + |E|)
• negative Kante
• negativer Zyklus
• 구현 가정 (implementation assumption)

Dijkstra는 \(w(u,v) \ge 0\)w(u,v) ≥ 0에서 최솟값 추출을 사용하는 그리디 SSSP이다. Bellman-Ford는 음수 간선을 허용하며 반복 완화와 도달 가능한 음수 사이클 검출을 사용하는 SSSP이다.

강의 기준 Fibonacci 힙 Dijkstra는 \(\Theta(|V| \log |V| + |E|)\)Θ(|V| log |V| + |E|), Bellman-Ford는 \(\Theta(|V|\cdot |E|)\)Θ(|V|·|E|)이다.

Dijkstra는 가중치 0을 허용하지만 음수 간선은 허용하지 않는다. Bellman-Ford는 음수 간선을 허용하지만 도달 가능한 음수 사이클을 통과하는 유한한 답은 없다.

각 보기를 전제, 실행시간, 그래프 모양, 실패 조건에 관한 주장으로 표시한다. 그다음 정확한 단어 `nur`와 |E| 항의 누락 여부를 확인한다.