정확히 k 개의 간선이 있는 최단 경로

각 정점 쌍 사이의 가중치와 함께 하나의 유향 그래프가 제공되며 두 개의 정점 u 및 v도 제공됩니다. 우리의 임무는 꼭짓점 u에서 꼭짓점 v까지의 최단 거리와 정확히 k개의 모서리 수를 찾는 것입니다.

이 문제를 해결하기 위해 정점 u에서 시작하여 모든 인접 정점으로 이동하고 k 값을 k - 1로 사용하여 인접 정점에 대해 반복합니다.

입력 및 출력

Input:
The cost matrix of the graph.
0 10 3 2
∞  0 ∞ 7
∞  ∞ 0 6
∞  ∞ ∞ 0

Output:
Weight of the shortest path is 9

알고리즘

shortKEdgePath(u, v, edge)

입력 - 정점 u와 v, 그리고 여러 모서리.

출력 - 최단 경로의 거리입니다.

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

예시

#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) {
   if (edge == 0 && u == v)    //when 0 edge, no path is present            
      return 0;
   if (edge == 1 && cost[u][v] != INF)    //when only one edge, and (u,v) is valid
      return cost[u][v];
   if (edge <= 0)    //when edge is -ve, there are infinity solution        
      return INF;
   int shortPath = INF;

   for (int i = 0; i < NODE; i++) {    //for all vertices i, adjacent to u
      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