정확히 k개의 간선을 사용하는 최단 경로 찾기

문제 개요

각 정점 쌍 사이의 가중치가 주어진 방향 그래프(directed graph)가 있고, 두 개의 정점 u와 v가 주어집니다. 우리의 과제는 정확히 k개의 간선을 사용하여 정점 u에서 정점 v까지 이동하는 최단 경로의 거리(가중치 합)를 구하는 것입니다.

접근 방법

이 문제는 재귀적으로 접근할 수 있습니다. 시작 정점 u에서 출발하여 인접한 모든 정점으로 이동하고, 남은 간선 수를 하나 줄여(k-1) 다시 재귀 호출하는 방식입니다. 이렇게 하면 간선 수가 정확히 k개가 되는 모든 경로를 탐색하면서 그중 가중치의 합이 가장 작은 경로를 찾을 수 있습니다.

탐색 과정에서 중요한 종료 조건은 다음과 같습니다.

• 남은 간선 수가 0이고 현재 위치가 목적지 v라면, 경로가 완성된 것이므로 0을 반환합니다.
• 남은 간선 수가 1이고 u에서 v로 가는 간선이 존재한다면, 해당 간선의 가중치를 반환합니다.
• 남은 간선 수가 0보다 작아지면 유효한 경로가 없으므로 무한대(∞)를 반환합니다.

입력과 출력

입력:
그래프의 비용 행렬(cost matrix)
0 10 3 2
∞  0 ∞ 7
∞  ∞ 0 6
∞  ∞ ∞ 0

출력:
Weight of the shortest path is 9

알고리즘

shortKEdgePath(u, v, edge)

입력 − 정점 u와 v, 그리고 사용해야 할 간선의 수(edge).

출력 − 최단 경로의 거리.

Begin
   if edge = 0 and u = v, then
      return 0
   if edge = 1 and cost[u, v] ≠ ∞, then
      return cost[u, v]
   if edge <= 0, then
      return ∞
   set shortPath := ∞

   for all vertices i, do
      if cost[u, i] ≠ ∞ and u ≠ i and v ≠ i, then
         tempRes := shortKEdgePath(i, v, edge - 1)
         if tempRes ≠ ∞, then
            shortPath = minimum of shortPath and (cost[u,i]+tempRes
   done
   return shortPath
End

C++ 구현 예제

#include <iostream>
#define NODE 4
#define INF INT_MAX
using namespace std;

int cost[NODE][NODE] = {
   {0, 10, 3, 2},
   {INF, 0, INF, 7},
   {INF, INF, 0, 6},
   {INF, INF, INF, 0}
};

int minimum(int a, int b) {
   return (a<b)?a:b;
}

int shortKEdgePath(int u, int v, int edge) {
   // 간선 수가 0이면 더 이상 이동 불가 — 현재 위치가 목적지일 때만 0 반환
   if (edge == 0 && u == v)
      return 0;
   // 간선이 하나 남았고 (u, v) 간선이 존재하면 그 가중치 반환
   if (edge == 1 && cost[u][v] != INF)
      return cost[u][v];
   // 남은 간선 수가 음수이면 유효한 경로 없음
   if (edge <= 0)
      return INF;
   int shortPath = INF;

   // u에 인접한 모든 정점 i에 대해 재귀 탐색
   for (int i = 0; i < NODE; i++) {
      if (cost[u][i] != INF && u != i && v != i) {
         int tempRes = shortKEdgePath(i, v, edge-1);
         if (tempRes != INF)
            shortPath = minimum(shortPath, cost[u][i] + tempRes);
      }
   }
   return shortPath;
}

int main() {
   int src = 0, dest = 3, k = 2;
   cout << "Weight of the shortest path is " << shortKEdgePath(src, dest, k);
}

실행 결과

Weight of the shortest path is 9

위 예제에서 정점 0에서 정점 3까지 정확히 2개의 간선을 사용하는 경로 중 최단 경로는 0 → 2 → 3으로, 가중치의 합은 3 + 6 = 9입니다.