ขั้นตอนวิธีการผลักดัน - ติดป้ายใหม่

ขั้นตอนวิธีการผลักดัน - ติดป้ายใหม่ () เป็นหนึ่งในกลไกที่มีประสิทธิภาพมากที่สุดเพื่อคำนวณการไหลสูงสุด

ขั้นตอนวิธี 
กำหนดให้การไหลของเครือข่าย G(V,E) ที่มีความจุจากปม u ไปยัง ปม v ให้เป็น c(u,v) , เราต้องการหาปริมาณการไหลสูงสุดจากจุดเริ่มต้นที่ปม s ไปยังจุดสิ้นสุดที่ปม t ภายในเครือข่าย
โดยใช้การดำเนินการ 2 อย่าง คือ การผลักดัน และ การติดป้ายใหม่ ดังนี้
 f(u,v) คือการไหลจากปม u ไปที่ปม v โดยให้ความจุที่ได้คือ c(u,v) − f(u,v)
 height(u) ถ้าเงื่อนไข height(u) > height(v) เราจะทำการผลักดันจากปม u ไปปม v เท่านั้น โดยที่ สำหรับทุกปม u จะทำให้ height(u) เป็นจำนวนเต็มที่ไม่ติดลบ
 excess(u) คือผลรวมการไหลทั้งเข้าและออกจาก u

ในแต่ละขึ้นตอนของขั้นตอนวิธีนั้น จะทำการไหลก่อนล่วงหน้า เพื่อให้ผลคำนวณเป็นไปตามที่เราต้องการ ดังนี้
 f(u,v) ≤ c(u,v) คือ การไหลจากปม u ไปปม v นั้น ต้องไม่เกินความจุจากปม u ไปปม v
 f(u,v) = -f(v,u) เราจะคงค่าการไหลไว้ คือ ไหลไปในทิศทางเดียว ถ้าไหลย้อนกลับ ค่าการไหลนั้นจะติดลบ ซึ่งก็คือ ไหลย้อนทางนั่นเอง
 ∑ f(v,u) = excess(u) ≥ 0 สำหรับปม u ≠ s ที่เป็นจุดเริ่มต้นของการไหลเท่านั้น
ขอให้สังเกตว่าเงื่อนไขที่ทำการไหลก่อนล่วงหน้านี้ เป็นการผ่อนคลายจากสภาพที่สอดคล้องกันสำหรับ กฎการไหล ในเครือข่ายของการไหลปกติ
เราสังเกตเห็นว่าเส้นทางที่ยาวมากที่สุดที่เป็นไปได้จากปม s ไปปม t คือ ขนาดของปม | V |
ดังนั้นเป็นไปได้ที่จะกำหนดความสูงให้กับปม ตามกฎของการไหล ดังนี้ height(s) = | V | และ height(t) = 0
และถ้าค่าการไหลจากปม u ไปปม v นั้นเป็นบวก คือ height(u) > height(v) เราจะปรับความสูงของปม เหมือนกับการไหลของน้ำที่ไหลลงพื้น
ความสูงของปม ( ยกเว้นปม s และปม t ) จะถูกปรับ และการไหลจะถูกส่งระหว่างปมจนกระทั่งถึงปม t จากนั้นเราจะทำการเพิ่มความสูงของปมที่อยู่ภายในจนกระทั่งทุกปมในเครือข่ายที่ไม่ถึงปม t มีการไหลย้อนกลับไปสู่ปม s
ปมสามารถทำให้ความสูงถึง 2| V | − 1 ก่อนที่จะเสร็จสมบูรณ์ คือ ความยาวสูงสุดที่เป็นไปได้ของเส้นทางที่กลับมาที่ปม s รวมปม t ด้วย ยาวเท่ากับ | V | − 1 และมี height(s) = | V |, height(t) = 0

การผลักดัน 
การผลักดันจากปม u ไปปม v ซึ่งหมายถึงการส่งส่วนหนึ่งของการไหลที่เกินจากปม u ไปปม v โดยทั้ง 3 เงื่อนไขข้างล่างนี้ต้องเป็นจริงจึงจะเกิดการผลักดัน
 excess(u) > 0 คือ การไหลเข้าปม u มากกว่า การไหลออกปม u
 c(u,v) − f(u,v) > 0 มีความจุที่เป็นค่าบวกจากปม u ไปปม v
 height(u) > height(v) คือ ต้องส่งผ่านไปยังปมที่ต่ำกว่าเท่านั้น
เราจะส่งปริมาณการไหลเท่ากับ min( excess(u), c(u,v) − f(u,v) )

การติดป้ายใหม่ 
ทำการติดป้ายใหม่บนปม u ที่เพิ่มขึ้นจนกว่าจะมีความสูงอย่างน้อย 1 ปมที่มีความจุที่มีค่าเป็นจำนวนบวก โดยมีเงื่อนไขของการติดป้ายใหม่ดังนี้
 excess(u) > 0 ต้องมีจุดที่ทำการติดป้ายใหม่ได้
 height(u) ≤ height(v) สำหรับทุกปม v ที่ c(u,v) − f(u,v) > 0 เฉพาะปมที่มีความจุสูงกว่า
เมื่อทำการติดป้ายใหม่นั้น เราจะทำการกำหนดให้ height(u) เป็นค่าที่น้อยที่สุด ดังที่ว่า height(u) > height(v) สำหรับบางปม v ที่ c(u,v) − f(u,v) > 0

ขั้นตอนวิธีการผลักดัน - ติดป้ายใหม่ 
โดยทั่วไปมีรูปแบบดังต่อไปนี้
 ตราบใดที่ยังมีกฎการผลักดัน หรือ การดำเนินการติดป้ายใหม่ ให้ทำดังนั้
 ทำตามกฎการผลักดัน หรือ
 กฎการติดป้ายใหม่
เวลาการทำงานสำหรับขั้นตอนวิธีนี้อยู่ในรูปทั่วไป O(V2E) (อาร์กิวเมนต์ละเว้น)

การติดป้ายใหม่ทางด้านหน้า 
การติดป้ายด้านหน้าบนปม u ทำได้ดังนี้
 ตราบเท่าที่ excess(u) > 0
 หากยังไม่ติดป้ายใหม่ให้กับทุกปมที่มีเส้นเชื่อมต่อกับ u
 ให้ลองผลักดันในปมที่ยังไม่ได้ลอง
 ถ้าลองครบทุกปมแล้ว
 ให้ทำการติดป้ายที่ปม u ใหม่
ต้องทราบว่าตอนติดป้ายใหม่ครั้งล่าสุดนั้นเราได้ลองปมใดไปบ้าง

ขั้นตอนวิธีการติดป้ายใหม่ทางด้านหน้า โดยใช้การช่วยค้นหาแบบเข้ามาก่อนออกก่อน 
โดยมีลำดับการผลักดัน และ ติดป้ายใหม่ ดังนี้
 ส่งค่าการไหลที่มากที่สุดที่เป็นไปได้
 สร้างรายการของทุกปม ยกเว้นปม s และปม t
 ตราบเท่าที่เรายังไม่ได้ไปทุกปมที่อยู่ในรายการ ให้ทำดังนี้
 ติดป้ายใหม่ทางด้านหน้าให้กับปมปัจจุบัน
 ถ้าความสูงของปมปัจจุบันเปลี่ยนแปลง ให้ทำดังนี้
 ย้ายปมปัจจุบันไปไว้หน้าสุดของรายการ
 ทำการเริ่มต้นใหม่ตั้งแต่ปมแรกของรายการ
เวลาในการทำงานของการติดป้ายใหม่ทางด้านหน้า เป็น O(V3)

อ้างอิง 
 Thomas H. Cormen, Charles E. Leiserson, Ronald L. Rivest, and Clifford Stein. Introduction to Algorithms, Second Edition. MIT Press and McGraw-Hill, 2001. ISBN 0-262-03293-7. Section 26.4: Push-relabel algorithms, and section 26.5: The relabel-to-front-algorithm.
 Jon Kleinberg & Eva Tardos. Algorithm Design. Pearson International Edition. Addison Wesley, 2006. ISBN 0-321-37291-3. Section 7.4: The Preflow-Push Maximum-Flow Algorithm.

การไหลในเครือข่าย
ขั้นตอนวิธีกราฟ