ทำความรู้จักกับ Bellman-Ford Algorithm

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

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

การใช้งาน

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

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

อัลกอริธึม Bellman-Ford ทำการวนลูปจำนวนครั้งเท่ากับจำนวนโหนดในกราฟลบด้วยหนึ่ง ([V - 1] iterations) และในทุก ๆ การวนลูป อัลกอริธึมจะทำการสำรวจทุกขอบ (edge) ในกราฟ จึงส่งผลให้มีความซับซ้อนโดยรวมอยู่ที่ O(V * E) ซึ่ง V คือจำนวนโหนด และ E คือจำนวนขอบ

ข้อดีและข้อเสีย

- สามารถจัดการกับกราฟที่มีค่าคะแนนติดลบได้

- สามารถใช้งานง่ายและเป็นที่นิยมในหลาย ๆ เขียนโปรแกรม

- เปรียบเทียบกับ Dijkstra's Algorithm อาจช้ากว่าในกราฟที่ไม่มีค่าคะแนนติดลบ โดยเฉพาะในกราฟที่มีขนาดใหญ่

ตัวอย่างโค้ดใน Swift

ตอนนี้เรามาดูตัวอย่างโค้ดในการใช้ Bellman-Ford Algorithm กันบ้าง เพื่อช่วยในการทำความเข้าใจ:

 import Foundation

class Edge {
    var source: Int
    var destination: Int
    var weight: Int

    init(source: Int, destination: Int, weight: Int) {
        self.source = source
        self.destination = destination
        self.weight = weight
    }
}

class Graph {
    var vertices: Int
    var edges: [Edge] = []

    init(vertices: Int) {
        self.vertices = vertices
    }

    func addEdge(source: Int, destination: Int, weight: Int) {
        let edge = Edge(source: source, destination: destination, weight: weight)
        edges.append(edge)
    }

    func bellmanFord(source: Int) {
        var distances = [Int](repeating: Int.max, count: vertices)
        distances[source] = 0

        for _ in 1..<vertices {
            for edge in edges {
                if distances[edge.source] != Int.max &&
                   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 &&
               distances[edge.source] + edge.weight < distances[edge.destination] {
                print("Graph contains negative weight cycle")
                return
            }
        }

        print("Vertex Distance from Source")
        for i in 0..<vertices {
            print("\(i)\t\t\(distances[i])")
        }
    }
}

// ตัวอย่างการใช้งาน
let graph = Graph(vertices: 5)
graph.addEdge(source: 0, destination: 1, weight: -1)
graph.addEdge(source: 0, destination: 2, weight: 4)
graph.addEdge(source: 1, destination: 2, weight: 3)
graph.addEdge(source: 1, destination: 3, weight: 2)
graph.addEdge(source: 1, destination: 4, weight: 2)
graph.addEdge(source: 3, destination: 2, weight: 5)
graph.addEdge(source: 3, destination: 1, weight: 1)
graph.addEdge(source: 4, destination: 3, weight: -3)

graph.bellmanFord(source: 0)

สรุป

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

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