DAA - กราฟหลายขั้นตอน
กราฟหลายขั้นตอน G = (V, E) เป็นกราฟกำกับที่จุดยอดถูกแบ่งออกเป็น k (ที่ไหน k > 1) จำนวนส่วนย่อยที่ไม่ปะติดปะต่อกัน S = {s1,s2,…,sk}เช่นนั้น edge (u, v)อยู่ใน E ดังนั้นu Є s iและv Є s 1 + 1สำหรับเซตย่อยบางส่วนในพาร์ติชันและ |s1| = |sk| = 1.
จุดยอด s Є s1 เรียกว่า source และจุดยอด t Є sk ถูกเรียก sink.
Gมักจะถือว่าเป็นกราฟถ่วงน้ำหนัก ในกราฟนี้ค่าใช้จ่ายของขอบ(ฉัน j)เป็นตัวแทนจากค (I, J) ดังนั้นค่าใช้จ่ายของเส้นทางจากแหล่งที่มาs จม t คือผลรวมของต้นทุนของแต่ละขอบในเส้นทางนี้
ปัญหาของกราฟหลายขั้นตอนคือการค้นหาเส้นทางที่มีต้นทุนขั้นต่ำจากต้นทาง s จม t.
ตัวอย่าง
พิจารณาตัวอย่างต่อไปนี้เพื่อทำความเข้าใจแนวคิดของกราฟหลายขั้นตอน
ตามสูตรเราต้องคำนวณต้นทุน (i, j) โดยใช้ขั้นตอนต่อไปนี้
ขั้นตอนที่ 1: ค่าใช้จ่าย (K-2, j)
ในขั้นตอนนี้สามโหนด (โหนด 4, 5. 6) ถูกเลือกเป็น j. ดังนั้นเรามีสามทางเลือกในการเลือกต้นทุนขั้นต่ำในขั้นตอนนี้
ต้นทุน (3, 4) = ขั้นต่ำ {c (4, 7) + ต้นทุน (7, 9), ค (4, 8) + ต้นทุน (8, 9)} = 7
ต้นทุน (3, 5) = ขั้นต่ำ {c (5, 7) + ต้นทุน (7, 9), ค (5, 8) + ต้นทุน (8, 9)} = 5
ต้นทุน (3, 6) = ขั้นต่ำ {c (6, 7) + ต้นทุน (7, 9), ค (6, 8) + ต้นทุน (8, 9)} = 5
ขั้นตอนที่ 2: ค่าใช้จ่าย (K-3, j)
สองโหนดถูกเลือกเป็น j เนื่องจากในระยะ k - 3 = 2 มีสองโหนด 2 และ 3 ดังนั้นค่า i = 2 และ j = 2 และ 3
ต้นทุน (2, 2) = ขั้นต่ำ {c (2, 4) + ต้นทุน (4, 8) + ต้นทุน (8, 9), ค (2, 6) +
ต้นทุน (6, 8) + ต้นทุน (8, 9)} = 8
ต้นทุน (2, 3) = {c (3, 4) + ต้นทุน (4, 8) + ต้นทุน (8, 9), ค (3, 5) + ต้นทุน (5, 8) + ต้นทุน (8, 9), c (3, 6) + ต้นทุน (6, 8) + ต้นทุน (8, 9)} = 10
ขั้นตอนที่ 3: ค่าใช้จ่าย (K-4, j)
ต้นทุน (1, 1) = {c (1, 2) + ต้นทุน (2, 6) + ต้นทุน (6, 8) + ต้นทุน (8, 9), c (1, 3) + ต้นทุน (3, 5) + ต้นทุน (5, 8) + ค่าใช้จ่าย (8, 9))} = 12
c (1, 3) + ต้นทุน (3, 6) + ต้นทุน (6, 8 + ต้นทุน (8, 9))} = 13
ดังนั้นเส้นทางที่มีต้นทุนขั้นต่ำคือ 1→ 3→ 5→ 8→ 9.