Số đường đi từ nguồn đến đích với đúng k cạnh

Giới thiệu

Một đồ thị có hướng được cho. Hai đỉnh u và v cũng được cho, u là đỉnh bắt đầu, v là đỉnh kết thúc. Nhiệm vụ của ta là tìm số đường đi từ đỉnh u đến v với đúng k cạnh. Giá trị k cũng được cung cấp trong thuật toán.

Bằng cách sử dụng quy hoạch động, ta cần tạo một bảng 3D, nơi hàng sẽ chỉ giá trị của u, cột sẽ chỉ giá trị của v và chiều sâu sẽ dùng để theo dõi số cạnh từ đầu đến cuối.

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

Đầu vào: Ma trận kề của đồ thị: Đỉch đích là 3. K = 2
0 1 1 1
0 0 0 1
0 0 0 1
0 0 0 0
Đầu ra: Có 2 Đường đi có thể, từ 0 đến 3 với 2 cạnh.

Thuật toán

numberOdWalks(u, v, k)
Đầu vào: Đỉnh bắt đầu u, đỉnh kết thúc v, số cạnh k.
Đầu ra: Số đường đi có thể với k cạnh.

Begin
    định nghĩa mảng 3D count cấp (n x n x k+1)
    // n là số đỉnh
    for edge in range 0 to k, do
        for i in range 0 to n-1, do
            for j in range 0 to n-1, do
                count[i, j, edge] := 0
                if edge = 0 and i = j, then
                    count[i, j, edge] := 1
                if edge = 1 and (i, j) is connected, then
                    count[i, j, edge] := 1
                if edge > 1, then
                    for a in range 0 to n, and adjacent with i do
                        count[i, j, edge] := count[i, j, edge] + count[a, j, edge - 1]
                    done
                done
            done
        done
    done
    return count[u, v, k]
End

Ví dụ (C++)

#include <iostream>
#define NODE 7
using namespace std;

int graph[NODE][NODE] = {
    {0, 1, 1, 1},
    {0, 0, 0, 1},
    {0, 0, 0, 1},
    {0, 0, 0, 0}
};

int numberOfWalks(int u, int v, int k) {
    int count[NODE][NODE][k+1];
    for (int edge = 0; edge <= k; edge++) {
        // cho k cạnh (0..k)
        for (int i = 0; i < NODE; i++) {
            for (int j = 0; j < NODE; j++) {
                count[i][j][edge] = 0;  // ban đầu tất cả giá trị là 0
                if (edge == 0 && i == j)  // khi e là 0 và node i và j giống nhau, chỉ có một đường
                    count[i][j][edge] = 1;
                if (edge == 1 && graph[i][j])  // khi e là 0 và đường trực tiếp từ (i đến j), một đường
                    count[i][j][edge] = 1;
                if (edge > 1) {
                    // cho nhiều hơn một cạnh
                    for (int a = 0; a < NODE; a++)  // kề của nguồn i
                        if (graph[i][a])
                            count[i][j][edge] += count[a][j][edge-1];
                }
            }
        }
    }
    return count[u][v][k];
}

int main() {
    int u = 0, v = 3, k = 2;
    cout << "There are " << numberOfWalks(u, v, k) << " Possible Walks, from ";
    cout << u << " to " << v << " with " << k << " edges.";
}

Kết quả

There are 2 Possible Walks, from 0 to 3 with 2 edges.