Đường đi ngắn nhất qua k cạnh

U2Ber · November 27, 2018, 9:56am

Cho một đồ thị có hướng gồm n đỉnh được đánh số từ 1 đến n và m cạnh có hướng với trọng số. Bạn hãy tính độ dài của đường đi ngắn nhất qua đúng k cạnh giữa mọi cặp đỉnh, với k cho trước.

Ví dụ với đồ thị cho trong hình vẽ sau:

Độ dài đường đi ngắn nhất qua đúng 4 cạnh giữa mọi cặp đỉnh được cho trong ma trận sau. Số ở hàng i , cột j là độ dài đường đi ngắn nhất qua đúng 4 cạnh từ đỉnh i đến đỉnh j , ở đó hiệu ∞ biểu thị không có đường đi.

∞	∞	10	11	9	∞
9	∞	∞	∞	8	9
∞	11	∞	∞	∞	∞
∞	8	∞	∞	∞	∞
∞	∞	∞	∞	∞	∞
∞	∞	12	13	11	∞

Chú ý rằng có thể có nhiều hơn 1 cạnh hướng từ đỉnh này đến đỉnh kia và thậm chí có thể có nhiều hơn 1 cạnh hướng từ một đỉnh đến chính nó.

hungaya · November 27, 2018, 2:48pm

Gọi P^k_ij là đường đi ngắn nhất (path) từ đỉnh i đến đỉnh j có số cạnh là k, số đỉnh đi qua là k+1.
Ví dụ:

P¹₄₂ = 1: đường đi ngắn nhất từ đỉnh 4 sang đỉnh 2 có số cạnh 1 và số đỉnh là 2, biểu diễn là (4, 2)
P¹₁₂ = ∞: đường đi ngắn nhất từ đỉnh 1 sang đỉnh 2 có số cạnh 1 và số đỉnh là 2, biểu diễn là (1, 2)
P⁴₁₅ = 9: đường đi ngắn nhất từ đỉnh 1 sang đỉnh 5 có số cạnh 4 và số đỉnh là 5, biểu diễn là (1, 4, 2, 6, 2)

Chỉ cần chạy vòng for từ t = 2 tới k. Lần lặp t tính toán tất cả giá trị P^t_ij, công thức như sau:

Khởi tạo P^t_ij = ∞
P^t_ij = min( P^t-1_im + P¹_mj, P^t-2_im + P²_mj, P^t-3_im + P³_mj,… )
- P^t-n_im != ∞, Pⁿ_mj != ∞, với 0 <= m, n < số đỉnh.

Ban đầu:

P¹_ij = trọng số cạnh từ i tới j, nếu có cạnh từ i tới j
P¹_ij = ∞, nếu không có cạnh từ i tới j

Chạy xong for thì lấy các giá trị P^k_ij != ∞.

JavaScript

function shortestPath(nVertex, pathLength, edges) {
  let paths = [];

  function createPaths() {
    function createMatrix() {
      let m = [];
      for (let i = 0; i < nVertex; i++) {
        m[i] = [];
        for (let j = 0; j < nVertex; j++) {
          m[i][j] = null;
        }
      }
      return m;
    }

    for (let i = 0; i < pathLength; i++) {
      paths[i] = createMatrix();
    }
  }

  function initP1() {
    for (let e of edges) {
      paths[0][e.src][e.des] = e.wei;
    }
  }

  function findKPath() {
    function min(a, b) {
      return a - b > 0 ? b : a;
    }

    for (let k = 1; k < pathLength; k++) {
      for (let i = 0; i < nVertex; i++) {
        for (let j = 0; j < nVertex; j++) {
          for (let m = 0; m < nVertex; m++) {
            for (let ik = 0; ik <= Math.floor(k/2); ik++) {
              left = paths[ik][i][m];
              if (left) {
                right = paths[k-ik-1][m][j];
                if (right) {
                  if (paths[k][i][j]) {
                    paths[k][i][j] = min(paths[k][i][j], left + right);
                  } else {
                    paths[k][i][j] = left + right;
                  }
                }
              }
            }
          }
        }
      }
    }
  }

  function getKPaths() {
    let edges = [];
    const k = pathLength - 1;
    let value;
    for (let i = 0; i < nVertex; i++) {
      for (let j = 0; j < nVertex; j++) {
        value = paths[k][i][j];
        if (value) {
          edges.push({ src: i, des: j, wei: value });
        }
      }
    }
    return edges;
  }

  createPaths();
  initP1();
  findKPath();
  return getKPaths();
}

let paths = shortestPath(
  6,
  4,
  [
    { src: 0, des: 3, wei: 4 },
    { src: 1, des: 0, wei: 2 },
    { src: 1, des: 4, wei: 1 },
    { src: 1, des: 5, wei: 2 },
    { src: 2, des: 1, wei: 4 },
    { src: 3, des: 1, wei: 1 },
    { src: 5, des: 2, wei: 3 },
    { src: 5, des: 4, wei: 2 }
  ]
);

for (p of paths) {
  console.log(p);
}

Note: lười code C++

∞	∞	10	11	9	∞
9	∞	∞	∞	8	9
∞	11	∞	∞	∞	∞
∞	8	∞	∞	∞	∞
∞	∞	∞	∞	∞	∞
∞	∞	12	13	11	∞

∞	∞	10	11	9	∞
9	∞	∞	∞	8	9
∞	11	∞	∞	∞	∞
∞	8	∞	∞	∞	∞
∞	∞	∞	∞	∞	∞
∞	∞	12	13	11	∞

∞	∞	10	11	9	∞
9	∞	∞	∞	8	9
∞	11	∞	∞	∞	∞
∞	8	∞	∞	∞	∞
∞	∞	∞	∞	∞	∞
∞	∞	12	13	11	∞