11 / 14강

최단 경로와 최소 신장 트리

세 건물을 잇는 통로가 있습니다. A와 B 사이의 비용은 2, B와 C 사이도 2, A와 C 사이는 3입니다. 한 곳에 빨리 도착하기와 모든 건물을 싸게 연결하기는 서로 다른 문제입니다.

   A -----3----- C
    \           /
     2         2
      \       /
          B

A에서 C로 가장 싸게 이동하기

직접 가면 비용이 3입니다. B를 거치면 2 + 2 = 4입니다. 따라서 최단 경로는 A에서 C로 바로 가는 길입니다. 여기서 ‘최단’은 간선에 적힌 비용의 합이 가장 작다는 뜻입니다.

가중치가 모두 0 이상이면 다익스트라 알고리즘을 사용할 수 있습니다.

1. 시작점의 거리를 0, 나머지는 아직 모르는 값인 무한대로 둡니다.
2. 아직 확정하지 않은 정점 중 현재 거리가 가장 작은 정점을 고릅니다.
3. 그 정점을 거쳐 가는 편이 더 싸면 이웃의 거리를 줄입니다. 이를 완화(relaxation)라고 합니다.
4. 도달 가능한 정점을 처리할 때까지 반복합니다.

예제에서는 A를 처리한 뒤 B는 2, C는 3입니다. B를 통해 C로 가는 비용 4는 현재 값 3보다 크므로 바꾸지 않습니다. 음수 가중치가 있으면 이 확정 방식이 성립하지 않을 수 있습니다.

모든 건물을 가장 싸게 연결하기

신장 트리는 모든 정점을 연결하면서 사이클이 없는 구조입니다. 정점이 V개라면 간선은 V-1개입니다. 연결된 무방향 그래프에서 간선 비용 합이 가장 작은 신장 트리를 **최소 신장 트리(MST)**라고 합니다.

예제에서는 A-B와 B-C를 골라 총비용 4로 모두 연결합니다. A-C까지 더하면 비용이 늘고 사이클이 생깁니다. 이 MST 안에서 A에서 C로 이동하는 비용은 4입니다. 원래 그래프의 최단 경로 비용 3과 다릅니다.

• 크루스칼: 가벼운 간선부터 보며, 사이클을 만들지 않는 간선을 고릅니다.
• 프림: 이미 연결한 정점 집합에서 바깥 정점으로 이어지는 가장 가벼운 간선을 붙입니다.

확인 문제

도시 전체에 통신선을 최소 비용으로 깔려는 문제와, 집에서 학교까지 최소 시간으로 가려는 문제는 각각 무엇에 가깝나요?