เข้าใจและประยุกต์ใช้ Bellman-Ford Algorithm ด้วยภาษา VBA

 

 

Bellman-Ford Algorithm คืออะไร?

Bellman-Ford Algorithm เป็นหนึ่งในอัลกอริธึมที่ใช้ในการหาค่าทางสั้นที่สุด (Shortest Path) จากจุดเริ่มต้นไปยังจุดปลายบนกราฟที่สามารถมีน้ำหนักเชิงลบ (Negative Weights) ได้ อัลกอริธึมนี้ถูกพัฒนาขึ้นในปี 1958 โดย Richard Bellman และ Lester Ford ซึ่งเป็นที่มาของชื่ออัลกอริธึม

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

 

การทำงานของ Bellman-Ford Algorithm

Bellman-Ford Algorithm ใช้วิธีการ "Relaxation" ซึ่งจะช่วยให้เราอัปเดตระยะทางที่คาดหวังจากต้นทางไปยังจุดอื่น ๆ ในกราฟ ในทุก ๆ รอบ เราจะตรวจสอบทุกขอบ (Edge) ของกราฟเพื่อลดระยะทางที่บ้านจากต้นทางให้เหลือน้อยที่สุด

ขั้นตอนการทำงาน

1. เริ่มต้นโดยการตั้งค่าระยะทางจากจุดเริ่มต้นไปยังจุดอื่นทั้งหมดให้เป็นอนันต์ (Infinity) ยกเว้นจุดเริ่มต้นที่จะตั้งค่าเป็น 0

2. ทำการวนซ้ำตามจำนวนของจุดบนกราฟ (V-1) แถว

3. ในแต่ละรอบ ให้ทำการตั้งค่าแต่ละขอบและทำการ Relaxation

4. ตรวจสอบว่ามีการพบวงจรเชิงลบ (Negative Cycle) หรือไม่

 

ตัวอย่างโค้ด Bellman-Ford ด้วยภาษา VBA

ต่อไปนี้คือโค้ดตัวอย่าง Bellman-Ford Algorithm ที่เขียนด้วยภาษา VBA

 Option Explicit

Const INFINITY As Double = 1E+30

Sub BellmanFord()
    Dim graph() As Variant
    Dim distances() As Double
    Dim predecessor() As Long
    Dim src As Long
    Dim i As Long, j As Long

    ' กำหนดกราฟ
    graph = Array( _
        Array(0, 1, -1), _
        Array(0, 2, 4), _
        Array(1, 2, 3), _
        Array(1, 3, 2), _
        Array(1, 4, 2), _
        Array(3, 2, 5), _
        Array(3, 1, 1), _
        Array(4, 3, -3) _
    ) ' (จุดเริ่มต้น, จุดสิ้นสุด, น้ำหนัก)

    ' กำหนดจุดเริ่มต้น
    src = 0
    ReDim distances(0 To UBound(graph, 1))
    ReDim predecessor(0 To UBound(graph, 1))

    ' กำหนดระยะทางเริ่มต้น
    For i = 0 To UBound(distances)
        distances(i) = INFINITY
        predecessor(i) = -1
    Next i
    distances(src) = 0

    ' ทำการ Relaxation
    For i = 0 To UBound(graph, 1) - 1
        For j = 0 To UBound(graph)
            Dim u As Long, v As Long, weight As Double
            u = graph(j)(0)
            v = graph(j)(1)
            weight = graph(j)(2)

            If distances(u) <> INFINITY And distances(u) + weight < distances(v) Then
                distances(v) = distances(u) + weight
                predecessor(v) = u
            End If
        Next j
    Next i

    ' เช็ควงจรเชิงลบ
    For j = 0 To UBound(graph)
        u = graph(j)(0)
        v = graph(j)(1)
        weight = graph(j)(2)

        If distances(u) <> INFINITY And distances(u) + weight < distances(v) Then
            Debug.Print "Negative cycle found!"
            Exit Sub
        End If
    Next j

    ' แสดงผลระยะทางที่สั้นที่สุด
    For i = 0 To UBound(distances)
        Debug.Print "Distance from source to " & i & " is " & distances(i)
    Next i
End Sub

วิธีการทำงานของโค้ด

1. การกำหนดกราฟ: ในตัวแปร `graph` เรากำหนดขอบ (Edge) ของกราฟ โดยเป็นรูปแบบอาร์เรย์ 2 มิติ (จุดเริ่มต้น, จุดสิ้นสุด, น้ำหนัก) 2. การตั้งค่าระยะทางเริ่มต้น: เรากำหนดระยะทางจากจุดเริ่มต้นให้เป็น 0 และจากจุดอื่นให้เป็นอนันต์ 3. การทำ Relaxation: เราจัดการอัพเดตระยะทางทุก ๆ ขอบในกราฟ โดยทำการเปรียบเทียบระยะทางที่คาดหวัง 4. การตรวจสอบวงจรเชิงลบ: หลังจากที่เราเสร็จสิ้นการทำ Relaxation จะมีการตรวจสอบเพื่อตรวจหาว่าวงจรเชิงลบอยู่ในกราฟหรือไม่

Use Case ในโลกจริง

การใช้ Bellman-Ford Algorithm นั้นสามารถพบได้ในสถานการณ์หลายรูปแบบ เช่น:

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

 

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

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

 

ข้อดีและข้อเสียของ Bellman-Ford Algorithm

ข้อดี:

1. สามารถจัดการกับกราฟที่มีน้ำหนักเชิงลบได้

2. ง่ายต่อการติดตามและจัดการการทำงาน

3. ให้ผลลัพธ์ที่ถูกต้องเมื่อตรวจสอบวงจรเชิงลบ

ข้อเสีย:

1. การทำงานช้าหากเปรียบเทียบกับ Dijkstra’s Algorithm สำหรับกราฟที่ไม่มีน้ำหนักเชิงลบ

2. ในกราฟที่มีจำนวนโหนดและขอบมาก ๆ อาจสร้างความล่าช้าในการประมวลผล

 

สรุป

Bellman-Ford Algorithm เป็นอีกทางเลือกที่มีประโยชน์ในการค้นหาทางที่สั้นที่สุดในกราฟ โดยเฉพาะเมื่อมีน้ำหนักเชิงลบ อย่าลืมว่าความรู้เกี่ยวกับอัลกอริธึมเหล่านี้ทำให้เราเข้าใจวิธีการแก้ปัญหาที่ซับซ้อนได้ดีขึ้น ถ้าหากคุณสนใจในการเรียนรู้ programming อย่างลึกซึ้ง EPT (Expert-Programming-Tutor) อาจเป็นทางเลือกที่ดี สัมผัสประสบการณ์และทักษะการเขียนโปรแกรมที่น่าตื่นเต้นได้ที่ EPT!

 

 

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