ทำความรู้จักกับ Bellman-Ford Algorithm และการใช้งานใน Kotlin

 

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

 

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

Bellman-Ford Algorithm เป็น Algorithm ที่ใช้ในการค้นหาเส้นทางที่สั้นที่สุดจากจุดเริ่มต้นไปยังจุดอื่นๆ ในกราฟที่อาจมีขอบที่มีน้ำหนักเชิงลบ (Negative Weight Edges) ซึ่งแตกต่างจาก Dijkstra's Algorithm ที่ทำงานได้ดีกับขอบแบบบวกเท่านั้น

การทำงานของ Algorithm นี้

:

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

2. ทำการวนรอบ N-1 ครั้ง (N คือจำนวนเวอร์ตซ์ในกราฟ) ประกาศให้แต่ละขอบ (Edge) ส่งผลในการอัปเดตระยะทางที่สั้นที่สุดจากจุดเริ่มต้น

3. หลังจากนั้นจะต้องตรวจสอบหากยังมีการอัปเดตระยะทางได้อีกครั้งหนึ่ง นั่นหมายความว่ากราฟมีวงจรลบ (Negative Cycle) ซึ่งถ้าเกิดขึ้นจะบอกได้ว่าไม่สามารถหาผลลัพธ์ที่ถูกต้องได้

 

ตัวอย่าง Code Bellman-Ford Algorithm ใน Kotlin

เพื่อให้เข้าใจได้ง่ายขึ้น เราจะมาดูตัวอย่างโค้ดของ Bellman-Ford Algorithm ที่เขียนโดยใช้ภาษา Kotlin กันดีกว่า

 data class Edge(val source: Int, val destination: Int, val weight: Int)

fun bellmanFord(edges: List<Edge>, vertices: Int, start: Int): IntArray {
    val distances = IntArray(vertices) { Int.MAX_VALUE }
    distances[start] = 0

    for (i in 1 until vertices) {
        for (edge in edges) {
            if (distances[edge.source] != Int.MAX_VALUE &&
                distances[edge.source] + edge.weight < distances[edge.destination]) {
                distances[edge.destination] = distances[edge.source] + edge.weight
            }
        }
    }

    // ตรวจสอบวงจรลบ
    for (edge in edges) {
        if (distances[edge.source] != Int.MAX_VALUE &&
            distances[edge.source] + edge.weight < distances[edge.destination]) {
            println("Graph contains negative weight cycle")
            return IntArray(0)
        }
    }

    return distances
}

// ตัวอย่างการใช้งาน
fun main() {
    val edges = listOf(
        Edge(0, 1, -1),
        Edge(0, 2, 4),
        Edge(1, 2, 3),
        Edge(1, 3, 2),
        Edge(1, 4, 2),
        Edge(3, 1, 1),
        Edge(3, 4, -3),
        Edge(4, 2, 5)
    )

    val vertices = 5
    val startVertex = 0
    val result = bellmanFord(edges, vertices, startVertex)

    if (result.isNotEmpty()) {
        for (i in result.indices) {
            println("Vertex $i has distance ${result[i]}")
        }
    }
}

 

การใช้งานในโลกจริง

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

1. การจำลองการขนส่งสินค้า: เมื่อต้องส่งสินค้าจากจุดต่างๆ ในเมืองที่มีอัตราค่าขนส่งแตกต่างกัน โดยอาจมีค่าธรรมเนียมที่ลดลงที่เป็นลบในการส่งสินค้าบางประเภท 2. ปัญหาการแข่งขันการเดินทาง: ในการกำหนดเส้นทางการเดินทางระหว่างสถานที่ต่างๆ ที่มีสถานการณ์ค่าใช้จ่ายที่ไม่แน่นอนหรือแม้กระทั่งมีการเปลี่ยนแปลงแบบเชิงลบ

 

วิเคราะห์ Complexity ของ Bellman-Ford Algorithm

Complexity ของ Bellman-Ford Algorithm จะถูกวิเคราะห์โดยพิจารณาทั้งจำนวนเวอร์ตซ์ (`V`) และจำนวนขอบ (`E`) ดังนี้:

- เวลา (Time Complexity): O(V * E) - พื้นที่ (Space Complexity): O(V)

ในการประเมินของ Time Complexity จะเกิดขึ้นเนื่องจากเราทำการวนรอบ Vertices (`V`) จำนวน N-1 ครั้ง และในแต่ละครั้งจะมีการวนผ่านขอบทั้งหมด (`E`)

 

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

ข้อดี:

1. รองรับกราฟที่มีน้ำหนักเชิงลบ: เป็นหนึ่งในไม่กี่ Algorithm ที่สามารถจัดการกับกราฟที่มีน้ำหนักเชิงลบได้ 2. ใช้งานง่าย: การนำเสนอ Algorithm ทำให้ไม่ต้องการโครงสร้างข้อมูลที่ซับซ้อนมากเกินไป

ข้อเสีย:

1. ประสิทธิภาพต่ำ: Comparatively slower than Dijkstra’s Algorithm, especially on larger graphs – you may find performance issues in heavy usage scenarios. 2. ไม่เหมาะสำหรับกราฟใหญ่: เนื่องจากเวลาในการทำลูปเป็น O(V * E) ย่อมทำให้มีความช้าลงถ้า {V} และ {E} เพิ่มขึ้นมากเกินไป

 

บทสรุป

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

หากคุณต้องการพัฒนาทักษะการเขียนโปรแกรมและเรียนรู้เรื่องเช่น Bellman-Ford Algorithm อย่างมีประสิทธิภาพ มาเรียนรู้กับเราที่ EPT ได้เลย!

 

 

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