จำนวนเส้นทางจากต้นทางไปปลายทางที่มี Edge ทั้งหมด k เส้น (Walks with Exactly K Edges)

บทนำ

กำหนด Directed Graph (กราฟมีทิศทาง) อีกสองจุด u และ v กำหนด u เป็นจุดเริ่มต้น และ v เป็นจุดสิ้นสุด ภารกิจคือหาจำนวนเส้นทาง (Walks) จากจุด u ไป v ที่มี Edge ทั้งหมด k เส้น ค่า k ก็ถูกกำหนดในอัลกอริทึม

ด้วยการใช้ Dynamic Programming เราต้องสร้างตาราง 3 มิติ (3D Table) โดยแถวจะชี้ค่า u คอลัมน์จะชี้ค่า v และมิติความลึก (Depth) จะใช้ติดตามจำนวน Edge จากต้นทางไปปลายทาง

อินพุตและเอาต์พุต

Input: Adjacency matrix ของกราฟ: จุดปลายทางคือ 3, K = 2
0 1 1 1
0 0 0 1
0 0 0 1
0 0 0 0
Output: มี 2 Possible Walks จาก 0 ถึง 3 ด้วย 2 edges

อัลกอริทึม

numberOdWalks(u, v, k)
Input: จุดเริ่มต้น u, จุดสิ้นสุด v, จำนวน edges k
Output: จำนวนเส้นทางที่เป็นไปได้กับ k edges

Begin
    กำหนดอาเรย์ 3D count ขนาด (n x n x k+1)  // n คือจำนวนจุด
    for edge ในช่วง 0 to k, do
        for i ในช่วง 0 to n-1, do
            for j ในช่วง 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) เชื่อมต่อ, then
                    count[i, j, edge] := 1
                if edge > 1, then
                    for a ในช่วง 0 to n, และ adjacent กับ i do
                        count[i, j, edge] := count[i, j, edge] + count[a, j, edge - 1]
                    done
            done
        done
    done
    return count[u, v, k]
End

ตัวอย่างโค้ด (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++) {
        // สำหรับ k edges (0..k)
        for (int i = 0; i < NODE; i++) {
            for (int j = 0; j < NODE; j++) {
                count[i][j][edge] = 0;  // เริ่มต้นค่าทั้งหมดเป็น 0
                if (edge == 0 && i == j)  // เมื่อ e=0 และโหนด i และ j เหมือนกัน มี path เดียว
                    count[i][j][edge] = 1;
                if (edge == 1 && graph[i][j])  // เมื่อ e=0 และมี path ตรงจาก (i ถึง j) มี path เดียว
                    count[i][j][edge] = 1;
                if (edge > 1) {
                    // สำหรับมากกว่าหนึ่ง edge
                    for (int a = 0; a < NODE; a++)  // adjacent ของ source 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.";
}

ผลลัพธ์

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