Đường đi ngắn nhất với đúng k cạnh

Một đồ thị có hướng được cung cấp với trọng số giữa mỗi cặp đỉnh, và hai đỉnh u và v cũng được cung cấp. Nhiệm vụ của ta là tìm khoảng cách ngắn nhất từ đỉnh u đến đỉnh v, với đúng k số lượng cạnh.

Để giải quyết bài toán này, ta sẽ bắt đầu từ đỉnh u và đi đến tất cả các đỉnh kề và đệ quy cho các đỉnh kề sử dụng giá trị k là k - 1.

Đầu vào và Đầu ra

Đầu vào: Ma trận chi phí của đồ thị.
0 10 3 2
∞  0  ∞  7
∞  ∞  0  6
∞  ∞  ∞  0
Đầu ra: Trọng số của đường đi ngắn nhất là 9

Thuật toán

shortKEdgePath(u, v, edge)
Đầu vào: Đỉnh u và v, và một số lượng cạnh.
Đầu ra: Khoảng cách của đường đi ngắn nhất.
Bắt đầu
  nếu edge = 0 và u = v thì
    trả về 0
  nếu edge = 1 và cost[u, v] ≠ ∞ thì
    trả về cost[u, v]
  nếu edge <= 0 thì
    trả về ∞
  đặt shortPath := ∞
  với mọi đỉnh i, thực hiện
    nếu cost[u, i] ≠ ∞ và u ≠ i và v ≠ i thì
      tempRes := shortKEdgePath(i, v, edge - 1)
      nếu tempRes ≠ ∞ thì
        shortPath = minimum của shortPath và (cost[u,i] + tempRes)
    kết thúc
  kết thúc
  trả về shortPath
Kết thúc

Ví dụ (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)
    // khi 0 cạnh, không có đường đi
    return 0;
  if (edge == 1 && cost[u][v] != INF)
    // khi chỉ một cạnh, và (u,v) hợp lệ
    return cost[u][v];
  if (edge <= 0)
    // khi cạnh âm, có vô nghiệm
    return INF;
  
  int shortPath = INF;
  for (int i = 0; i < NODE; i++) {
    // cho mọi đỉnh i kề với 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);
}

Đầu ra

Weight of the shortest path is 9