사용 개념: 다익스트라(배열 판), 벨만–포드 알고리즘, 플로이드 알고리즘의 경로 출력.

세 알고리즘의 손 계산은 같은 하위목표로 이루어진다. ① 처음 표 쓰기 ② 한 단계 고치기(무엇을 기준으로 어느 칸을 고치는지가 알고리즘마다 다르다) ③ 멈춤 확인 ④ 적어 둔 표로 길 읽기. 표는 길이를 적는 표와 길을 되짚을 표, 둘을 함께 채운다1.

  ② 한 단계 ④ 길을 되짚을 표
다익스트라 아직 안 고른 점 가운데 \(d\)가 가장 작은 점을 고르고, 그 점에서 나가는 간선으로 고친다 \(p[v]\) = \(v\) 바로 앞의 점. 도착점에서 거꾸로 따라간다
벨만–포드 윗줄의 값만 읽어 모든 간선으로 한 줄을 만든다 \(p(v, k)\). 마지막 줄을 거꾸로 따라간다
플로이드 거쳐 가도 되는 점 \(k\)를 하나 늘려 모든 칸을 고친다 \(kay(i, j)\) = 가운데의 한 점. 길을 둘로 가른다

−는 “아직 길이 없다(무한대)”는 뜻이다.

문제 1 · 완전한 풀이

점 1 ~ 7, 방향 간선과 비용이 다음과 같다. 1에서 모든 점까지 가장 짧은 길이를 다익스트라의 방법으로 구한다. \(d\)와 \(p\)는 배열로 두고, 고를 점은 배열을 훑어 찾는다.

1→3: 2    1→2: 6    1→4: 16   1→7: 14   3→2: 7    3→5: 3    3→6: 8
2→4: 5    2→5: 4    5→4: 4    5→7: 10   4→7: 3    6→7: 1
  1. 처음 표: \(d[1] = 0\)이고 나머지는 −다.
  2. 한 단계: 아직 안 고른 점 가운데 \(d\)가 가장 작은 점을 고른다. 그 점에서 나가는 간선 \((u, v)\)마다 \(d[u] + \text{비용}\)이 \(d[v]\)보다 작으면 \(d[v]\)를 고치고 \(p[v] = u\)로 적는다.
고른 점 \(d[1]\) ~ \(d[7]\) \(p[1]\) ~ \(p[7]\) 이 단계에서 고친 것
1 0, 6, 2, 16, −, −, 14 −, 1, 1, 1, −, −, 1 2, 3, 4, 7
3 0, 6, 2, 16, 5, 10, 14 −, 1, 1, 1, 3, 3, 1 5(2 + 3), 6(2 + 8). 2는 2 + 7 = 9가 6보다 커서 그대로
5 0, 6, 2, 9, 5, 10, 14 −, 1, 1, 5, 3, 3, 1 4(5 + 4). 7은 5 + 10 = 15가 14보다 커서 그대로
2 0, 6, 2, 9, 5, 10, 14 −, 1, 1, 5, 3, 3, 1 없음. 4는 6 + 5 = 11이 9보다 크다
4 0, 6, 2, 9, 5, 10, 12 −, 1, 1, 5, 3, 3, 4 7(9 + 3)
6 0, 6, 2, 9, 5, 10, 11 −, 1, 1, 5, 3, 3, 6 7(10 + 1)
7 0, 6, 2, 9, 5, 10, 11 −, 1, 1, 5, 3, 3, 6 없음
  1. 멈춤 확인: 일곱 점을 모두 골랐다. 고른 순서는 1, 3, 5, 2, 4, 6, 7이고 길이가 짧은 순서(0, 2, 5, 6, 9, 10, 11)다.
  2. 길 읽기: 7로 가는 길은 \(p[7] = 6\), \(p[6] = 3\), \(p[3] = 1\)을 거꾸로 이어 1 → 3 → 6 → 7이고 길이는 \(2 + 8 + 1 = 11\)이다. 4로 가는 길은 \(p[4] = 5\), \(p[5] = 3\)이라 1 → 3 → 5 → 4, 길이 9다.

7의 값은 14 → 12 → 11로 세 번 바뀌었다. “가장 싼 간선만 따라가기”로는 1 → 3 → 5 → 4 → 7(길이 12)을 얻어 틀린다.

검증 — 39_shortest-path-ladder_p4.py

문제 2 · 마지막 하위목표만 빈칸

점 1 ~ 6, 방향 간선과 비용이 다음과 같다. 6→2의 비용이 음수라 벨만–포드를 쓴다. 출발점은 1이다.

1→2: 3    1→4: 7    2→3: 4    2→4: 5    3→5: 3    3→6: 6    4→5: 9    4→6: 1    6→2: −6
  1. 처음 표: \(d(1, 0) = 0\)이고 나머지는 −다.
  2. 한 단계: \(d(v, k) = \min\{d(v, k-1),\ d(w, k-1) + \text{비용}(w, v)\}\). 윗줄의 값만 읽는다.
\(k\) \(d(1,k)\) ~ \(d(6,k)\) \(p(1,k)\) ~ \(p(6,k)\)
0 0, −, −, −, −, − −, −, −, −, −, −
1 0, 3, −, 7, −, − −, 1, −, 1, −, −
2 0, 3, 7, 7, 16, 8 −, 1, 2, 1, 4, 4
3 0, 2, 7, 7, 10, 8 −, 6, 2, 1, 3, 4
4 0, 2, 6, 7, 10, 8 −, 6, 2, 1, 3, 4
5 0, 2, 6, 7, 9, 8 −, 6, 2, 1, 3, 4
  1. 멈춤 확인: 점이 6개라 \(k = 5\)까지 채운다. \(k = 5\) 줄도 윗줄과 달라 일찍 멈추지 못한다.
  2. 길 읽기: 마지막 줄의 \(p\)로 5, 6, 3으로 가는 가장 짧은 길과 길이를 쓰라. __
답
  • 5: \(p = 3\), 3의 \(p = 2\), 2의 \(p = 6\), 6의 \(p = 4\), 4의 \(p = 1\). 거꾸로 이으면 1 → 4 → 6 → 2 → 3 → 5, 길이 \(7 + 1 - 6 + 4 + 3 = 9\).
  • 6: 1 → 4 → 6, 길이 \(7 + 1 = 8\).
  • 3: 1 → 4 → 6 → 2 → 3, 길이 \(7 + 1 - 6 + 4 = 6\).

5로 가는 길은 간선이 5개(\(n - 1\)개)다. 그래서 \(d(5, k)\)가 \(k = 5\)에서야 9가 된다.

문제 3 · 하위목표 절반이 빈칸

점 8개인 그래프에 플로이드의 방법을 끝까지 돌려 얻은 \(kay\) 표가 다음과 같다. \(kay(i, j)\)는 \(i\)에서 \(j\)로 가는 가장 짧은 길 위에서 번호가 가장 큰 중간 점이고, 0이면 간선 하나로 간다.

\(kay\) 1 2 3 4 5 6 7 8
1 0 4 0 0 4 8 8 5
2 8 0 8 5 0 8 8 5
3 7 0 0 5 0 0 6 5
4 8 0 8 0 2 8 8 5
5 8 4 8 0 0 8 8 0
6 7 7 7 7 7 0 0 7
7 0 4 1 1 4 8 0 0
8 7 7 7 7 7 0 6 0

4에서 3으로 가는 가장 짧은 길을 되짚는다. 필요한 간선의 비용은 4→2: 5, 2→5: 4, 5→8: 1, 8→6: 2, 6→7: 1, 7→1: 2, 1→3: 5다.

  1. 첫 갈림: \(kay(4, 3) = 8\). (4, 8)과 (8, 3)으로 가른다.
  2. (4, 8) 토막: __
  3. (8, 3) 토막: \(kay(8, 3) = 7\)이라 (8, 7)과 (7, 3)으로 가른다. \(kay(8, 7) = 6\)이고 (8, 6), (6, 7)은 0이다. \(kay(7, 3) = 1\)이고 (7, 1), (1, 3)은 0이다. 이 토막은 8 → 6 → 7 → 1 → 3이다.
  4. 길과 길이: __
답
  1. \(kay(4, 8) = 5\)라 (4, 5)와 (5, 8)로 가른다. \(kay(4, 5) = 2\)이고 (4, 2), (2, 5)는 0이다. \(kay(5, 8) = 0\)이다. 이 토막은 4 → 2 → 5 → 8이다.
  2. 길은 4 → 2 → 5 → 8 → 6 → 7 → 1 → 3이고 길이는 \(5 + 4 + 1 + 2 + 1 + 2 + 5 = 20\)이다. 가를 때마다 토막의 “가장 큰 중간 점”이 8 → 5와 7 → 2, 6, 1 → 0으로 줄어든다.
검증 — 39_shortest-path-ladder_p4.py

문제 4 · 독립 문제

점 1 ~ 5, 방향 간선과 비용이 다음과 같다. 출발점은 1이다.

1→2: 2    1→3: 5    3→2: −4    2→4: 3    4→5: 1    3→5: 6

(가) 문제 1의 방법(다익스트라, 고른 점은 다시 고치지 않는다, \(d\)가 같으면 번호가 작은 점을 먼저)으로 \(d\)를 구하라. (나) 벨만–포드의 \(d(v, k)\) 표를 \(k = 0\)부터 4까지 채우고 마지막 줄의 \(p\)를 쓰라. (다) 5로 가는 가장 짧은 길을 쓰고, (가)가 틀린 점을 모두 들어라. 왜 틀렸는가?

답

(가) 고르는 순서 1, 2, 3, 4, 5. 1을 고르면 \(d\) = 0, 2, 5, −, −. 2를 고르면 \(d[4] = 5\). 3을 고르면(3과 4가 5로 같아 번호가 작은 3) 3→2로 \(5 - 4 = 1\)이 나오지만 2는 이미 골라서 고치지 않고, \(d[5] = 11\). 4를 고르면 \(d[5] = 6\). 결과는 0, 2, 5, 5, 6이다.
(나)

\(k\) \(d(1,k)\) ~ \(d(5,k)\)
0 0, −, −, −, −
1 0, 2, 5, −, −
2 0, 1, 5, 5, 11
3 0, 1, 5, 4, 6
4 0, 1, 5, 4, 5

\(k = 2\) 줄의 \(d(4, 2) = 5\)는 윗줄의 \(d(2, 1) = 2\)에 3을 더한 것이다. 같은 줄의 1을 쓰면 안 된다. 마지막 줄의 \(p\)는 −, 3, 1, 2, 4다.
(다) \(p\)를 거꾸로 따라가면 5 ← 4 ← 2 ← 3 ← 1이라 길은 1 → 3 → 2 → 4 → 5, 길이 \(5 - 4 + 3 + 1 = 5\)다. (가)는 2, 4, 5를 틀렸다(2, 5, 6이라 했지만 맞는 값은 1, 4, 5). 다익스트라는 가장 가까운 2를 거리 2로 확정했는데, 더 먼 3을 거쳐 음수 간선을 타면 1로 준다. 2가 틀리니 2를 거쳐 가는 4와 5도 따라 틀린다. 벨만–포드의 네 줄은 모두 윗줄과 달라서 끝까지 채워야 한다.

검증 — 39_shortest-path-ladder_p4.py

  1. 모든 답은 문제 코드로 확인했다. ↩