เป็นไปได้ที่จะเดินจากต้นทางไปยังปลายทางที่มีขอบ k อย่างแน่นอน

ให้กราฟกำกับ ให้จุดยอดอีกสองจุด u และ v ด้วย u คือจุดยอดเริ่มต้น และ v คือจุดยอดสิ้นสุด งานของเราคือการหาจำนวนการเดินจากจุดยอด u ถึง v โดยมีขอบ k เท่ากัน ค่าของ k ยังอยู่ในอัลกอริธึมด้วย

เมื่อใช้โปรแกรมไดนามิก เราจำเป็นต้องสร้างตาราง 3 มิติ โดยที่แถวจะชี้ค่าของ u คอลัมน์จะชี้ค่า v และความลึกจะใช้เพื่อติดตามจำนวนขอบตั้งแต่ต้นจนจบ

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

Input:Adjacency matrix of the graph:จุดยอดปลายทางคือ 3 K =20 1 10 0 0 10 0 0 10 0 0 0Output:มี 2 ทางเดินที่เป็นไปได้ จาก 0 ถึง 3 โดยมี 2 ขอบ 
อัลกอริทึม
 
numberOdWalks(u, v, k)
 

 ป้อนข้อมูล: จุดยอดเริ่มต้น u จุดยอดสิ้นสุด v จำนวนขอบ k
 

 ผลลัพธ์: จำนวนก้าวที่เป็นไปได้ด้วย k ขอบ
 
เริ่มกำหนดจำนวนอาร์เรย์ 3 มิติของลำดับ (nxnx k+1) //n คือจำนวนจุดยอดสำหรับขอบในช่วง 0 ถึง k ทำเพื่อ i ในช่วง 0 ถึง n-1 ทำเพื่อ j ในช่วง 0 ถึง n -1 นับ[i, j, edge] :=0 ถ้า edge =0 และ i =j จากนั้นนับ[i, j, edge] :=1 ถ้า edge =1 และ (i, j) เชื่อมต่ออยู่ count[i, j, edge] :=1 ถ้า edge> 1 จากนั้นสำหรับ a ในช่วง 0 ถึง n และอยู่ติดกับ i นับ[i, j, edge] :=count[i, j, edge] + count [a, j, edge - 1] เสร็จแล้ว เสร็จแล้ว เสร็จแล้ว นับกลับ[u, v, k]สิ้นสุด
 
ตัวอย่าง
 
#include #define NODE 7using เนมสเปซ std;int กราฟ[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 [NODE][NODE][k+1]; สำหรับ (ขอบ int =0; ขอบ <=k; ขอบ ++) { // สำหรับขอบ k (0..k) สำหรับ (int i =0; i 1) { // สำหรับมากกว่าหนึ่งขอบสำหรับ (int a =0; a  
ผลลัพธ์
 
สามารถเดินได้ 2 ทาง จาก 0 ถึง 3 โดยมี 2 ขอบ