ทำความรู้จักกับ Bellman-Ford Algorithm และการประยุกต์ใช้ในภาษา ABAP

 

 

บทนำของ Bellman-Ford Algorithm

Bellman-Ford Algorithm ถือเป็นหนึ่งใน Algorithm ที่สำคัญในด้านการค้นหาเส้นทางที่สั้นที่สุดจากจุดเริ่มต้นไปยังจุดหมายในกราฟที่มีน้ำหนัก (Weighted Graph) โดยสามารถจัดการกับกราฟที่มีค่าเชื่อม (Edge) เป็นลบได้ ซึ่งแตกต่างจาก Dijkstra's Algorithm ที่ไม่สามารถจัดการในกรณีที่มีค่าเชื่อมติดลบได้

Bellman-Ford คืออะไร?

Bellman-Ford Algorithm เป็นวิธีการที่ใช้ในการหาค่าเส้นทางที่สั้นที่สุดจากโหนดเริ่มต้นไปยังโหนดอื่น ๆ ในกราฟที่มีน้ำหนัก โดยเฉพาะเมื่อกราฟนั้นอาจมีค่าเชื่อมที่เป็นลบ ซึ่ง Algorithm นี้มีความสามารถในการตรวจจับวงจรที่มีน้ำหนักรวมต่ำกว่า 0 (Negative Cycle) ได้ด้วย

วิธีการทำงาน

Algorithm นี้ทำงานด้วยการผสมผสานการวนลูปและการอัปเดตค่าที่สั้นที่สุดในแต่ละรอบ โดยจะทำการเชื่อมต่อจากโหนดเริ่มต้นไปยังโหนดอื่น ๆ ในแต่ละรอบมากที่สุด `V-1` ครั้ง (`V` คือจำนวนโหนดในกราฟ)

 

การประยุกต์ใช้ Bellman-Ford Algorithm ในภาษา ABAP

ให้เรามาดูตัวอย่างการเขียน Bellman-Ford Algorithm ในภาษา ABAP กัน:

 TYPES: BEGIN OF t_edge,
         src TYPE i,
         dest TYPE i,
         weight TYPE i,
       END OF t_edge.

DATA: lt_edges TYPE TABLE OF t_edge,
      lv_v     TYPE i,
      lv_e     TYPE i,
      lv_src   TYPE i,
      lt_dist   TYPE TABLE OF i,
      lt_pred   TYPE TABLE OF i.

" ตัวอย่างข้อมูลกราฟ
lv_v = 5.
lv_e = 8.

APPEND VALUE #( src = 0 dest = 1 weight = -1 ) TO lt_edges.
APPEND VALUE #( src = 0 dest = 2 weight = 4 ) TO lt_edges.
APPEND VALUE #( src = 1 dest = 2 weight = 3 ) TO lt_edges.
APPEND VALUE #( src = 1 dest = 3 weight = 2 ) TO lt_edges.
APPEND VALUE #( src = 1 dest = 4 weight = 2 ) TO lt_edges.
APPEND VALUE #( src = 3 dest = 2 weight = 5 ) TO lt_edges.
APPEND VALUE #( src = 3 dest = 1 weight = 1 ) TO lt_edges.
APPEND VALUE #( src = 4 dest = 3 weight = -3 ) TO lt_edges.

" การเริ่มต้นค่า
DATA(lv_initial_distance) = 99999. " ค่าเริ่มต้นสำหรับระยะทาง

" กำหนดระยะทางเริ่มต้น
LOOP AT lt_edges INTO DATA(lv_edge).
  APPEND lv_initial_distance TO lt_dist.
ENDLOOP.
" ตั้งค่าเริ่มต้น
READ TABLE lt_dist INDEX 1 TRANSPORTING NO FIELDS.
IF sy-subrc = 0.
  lt_dist[ 1 ] = 0. " ระยะทางจากโหนดเริ่มต้น = 0
ENDIF.

" ทำการวนลูปเพื่อหาทางที่สั้นที่สุด
DO lv_v - 1 TIMES.
  LOOP AT lt_edges INTO lv_edge.
    IF lt_dist[ lv_edge-src + 1 ] + lv_edge-weight < lt_dist[ lv_edge-dest + 1 ].
      lt_dist[ lv_edge-dest + 1 ] = lt_dist[ lv_edge-src + 1 ] + lv_edge-weight.
      " เพิ่มการเก็บประวัติการผ่าน
    ENDIF.
  ENDLOOP.
ENDDO.

" ตรวจสอบ Negative Cycle
LOOP AT lt_edges INTO lv_edge.
  IF lt_dist[ lv_edge-src + 1 ] + lv_edge-weight < lt_dist[ lv_edge-dest + 1 ].
    WRITE: / 'Graph contains a negative-weight cycle'.
    EXIT.
  ENDIF.
ENDLOOP.

" แสดงระยะทางที่สั้นที่สุด
WRITE: / 'Vertex Distance from Source'.
LOOP AT lt_dist INTO DATA(lv_distance) INDEX INTO DATA(lv_index).
  WRITE: / lv_index - 1, lv_distance.
ENDLOOP.

Use Case ของ Bellman-Ford Algorithm ในโลกจริง

1. เครือข่ายโทรศัพท์: Bellman-Ford Algorithm ใช้เพื่อค้นหาทางที่ดีที่สุดในการเชื่อมต่อหมายเลขโทรศัพท์ผ่านสายเชื่อมที่มีค่าใช้จ่ายที่แตกต่างกัน 2. การวางแผนเส้นทางขนส่ง: ใช้ในการคำนวณเส้นทางที่สั้นที่สุดในการขนส่งสินค้าในบริษัทโลจิสติกส์ ที่สามารถมีการเปลี่ยนแปลงน้ำหนักของเส้นทางในแต่ละวัน

การวิเคราะห์ Complexity

- Time Complexity: O(V * E) ซึ่ง `V` คือจำนวนโหนด และ `E` คือจำนวนเส้นเชื่อม - Space Complexity: O(V) ต้องใช้หน่วยความจำสำหรับเก็บการระยะทางที่สั้นที่สุดสำหรับทุกโหนด

ข้อดีของ Bellman-Ford Algorithm

- สามารถจัดการกับเส้นทางที่มีค่าใช้จ่ายติดลบได้

- ตรวจจับ Negative Cycle ได้อย่างมีประสิทธิภาพ

ข้อเสียของ Bellman-Ford Algorithm

- เวลาการทำงานช้ากว่า Dijkstra's Algorithm ในกรณีที่ไม่มี Edge ติดลบ

- ซับซ้อนในการใช้งานเมื่อเทียบกับ Algorithm อื่น ๆ

 

สรุป

Bellman-Ford Algorithm เป็นเครื่องมือที่สำคัญสำหรับการหาค่าเส้นทางที่สั้นที่สุดในกราฟที่มีค่าใช้จ่ายติดลบ และการเขียนโค้ดในภาษา ABAP สามารถทำให้คุณเข้าใจการทำงานของ Algorithm นี้ได้เป็นอย่างดี หากคุณสนใจเรียนรู้เรื่องการเขียนโปรแกรม การศึกษาเพิ่มเติมที่ EPT จะช่วยให้คุณเข้าใจถึง Algorithm และโค้ดต่าง ๆ ได้ลึกซึ้งมากขึ้น ซึ่งเป็นการเปิดโอกาสในการพัฒนาทักษะด้านการเขียนโปรแกรมของคุณอย่างต่อเนื่อง! ขอเชิญคุณมาร่วมเรียนรู้กับเราได้ที่ EPT ขอบคุณสำหรับการติดตามอ่านบทความของเรา!

 

 

หมายเหตุ: ข้อมูลในบทความนี้อาจจะผิด โปรดตรวจสอบความถูกต้องของบทความอีกครั้งหนึ่ง บทความนี้ไม่สามารถนำไปใช้อ้างอิงใด ๆ ได้ ทาง EPT ไม่ขอยืนยันความถูกต้อง และไม่ขอรับผิดชอบต่อความเสียหายใดที่เกิดจากบทความชุดนี้ทั้งทางทรัพย์สิน ร่างกาย หรือจิตใจของผู้อ่านและผู้เกี่ยวข้อง