เส้นทางสั้นที่สุดที่มีกี่เส้นเชื่อมพอดี (Shortest Path with Exactly k Edges)

กำหนดกราฟมีทิศทางที่มีน้ำหนัก และโหนด u, v ต้องการหาระยะทางสั้นที่สุดจาก u ไป v ที่ใช้เส้นเชื่อมพอดี k เส้น

วิธีแก้: เริ่มจาก u ไปยังโหนดติดกันทั้งหมด และเรียกซ้ำ (Recursive) ด้วย k-1

การรับค่าและแสดงผล

Input: เมทริกซ์ต้นทุน
0  10  3   2
INF 0 INF  7
INF INF 0   6
INF INF INF 0

u=0, v=3, k=2
Output: Weight of the shortest path is 9

อัลกอริทึม

shortKEdgePath(u, v, edge)

Begin
  if edge = 0 and u = v then return 0
  if edge = 1 and cost[u,v] ≠ INF then return cost[u,v]
  if edge <= 0 then return INF
  
  shortPath := INF
  for ทุกโหนด i do
    if cost[u,i] ≠ INF และ u ≠ i และ v ≠ i then
      tempRes := shortKEdgePath(i, v, edge - 1)
      if tempRes ≠ INF then
        shortPath := min(shortPath, cost[u,i] + tempRes)
      end if
    end if
  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) {
  if (edge == 0 && u == v) return 0;
  if (edge == 1 && cost[u][v] != INF) return cost[u][v];
  if (edge <= 0) return INF;
  
  int shortPath = INF;
  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