ทำความรู้จัก Bellman-Ford Algorithm ด้วยภาษา Groovy

 

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

 

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

Bellman-Ford Algorithm เป็นหนึ่งในวิธีการหาค่าทางสั้นที่สุด (Shortest Path) ในกราฟที่มีน้ำหนักเรียบกรม (Weighted Graph) ซึ่งสามารถรับมือกับกราฟที่มีขอบ (Edge) ที่มีน้ำหนักเชิงลบได้ อย่างไรก็ตาม มันไม่สามารถจัดการกับกราฟที่มีลูปลูบ (Negative Cycle) ได้

วิธีทำงานของ Bellman-Ford Algorithm

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

 

การใช้งานและ Use Case ในโลกจริง

Bellman-Ford Algorithm สามารถใช้ได้ในหลายๆ สถานการณ์ที่เกี่ยวข้องกับการหาทางสั้นที่สุดในกราฟ เช่น:

1. แผนที่นำทาง – ใช้ในการหาทางที่สั้นที่สุดระหว่างจุด A ถึงจุด B ในระบบแผนที่นำทาง 2. การวิเคราะห์การเงิน – ใช้เพื่อคำนวณต้นทุนที่ดีที่สุดในเครือข่ายการเงินที่อาจมีการกำหนดราคาที่แตกต่างกัน 3. ใช้ในเกม – ใช้ในการหาทางในการเคลื่อนที่ในเกมออนไลน์ที่มีกฎซับซ้อน

 

ตัวอย่างโค้ด Groovy

มาต่อกันที่ตัวอย่างโค้ดกันครับ โดยเราจะสร้างฟังก์ชันที่ใช้ Bellman-Ford Algorithm ในภาษา Groovy

 class Graph {
    int vertices
    List<Edge> edges

    Graph(int v) {
        this.vertices = v
        this.edges = []
    }

    void addEdge(int source, int destination, int weight) {
        edges << new Edge(source, destination, weight)
    }

    void bellmanFord(int startVertex) {
        int[] distance = new int[vertices]
        Arrays.fill(distance, Integer.MAX_VALUE)
        distance[startVertex] = 0

        // การวนลูปเพื่อหาทางสั้นที่สุด
        for (int i = 1; i < vertices; i++) {
            for (Edge edge : edges) {
                if (distance[edge.source] != Integer.MAX_VALUE && distance[edge.source] + edge.weight < distance[edge.destination]) {
                    distance[edge.destination] = distance[edge.source] + edge.weight
                }
            }
        }

        // ตรวจสอบลูปลูบ
        for (Edge edge : edges) {
            if (distance[edge.source] != Integer.MAX_VALUE && distance[edge.source] + edge.weight < distance[edge.destination]) {
                println("Graph contains negative weight cycle")
                return
            }
        }

        printSolution(distance)
    }

    void printSolution(int[] distance) {
        println("Vertex Distance from Source")
        for (int i = 0; i < distance.length; i++) {
            println("$i \t\t $distance[i]")
        }
    }
}

class Edge {
    int source
    int destination
    int weight

    Edge(int s, int d, int w) {
        this.source = s
        this.destination = d
        this.weight = w
    }
}

// การสร้างกราฟและการใช้งาน
Graph graph = new Graph(5)
graph.addEdge(0, 1, -1)
graph.addEdge(0, 2, 4)
graph.addEdge(1, 2, 3)
graph.addEdge(1, 3, 2)
graph.addEdge(1, 4, 2)
graph.addEdge(3, 2, 5)
graph.addEdge(3, 1, 1)
graph.addEdge(4, 3, -3)

graph.bellmanFord(0)

ในตัวอย่างนี้ เราได้สร้างกราฟที่มี 5 จุด และเพิ่มขอบที่มีน้ำหนักต่างๆ หลังจากนั้นเราเรียกใช้ `bellmanFord` โดยระบุจุดเริ่มต้นเป็น 0 และจากนั้นจะพิมพ์ระยะทางที่สั้นที่สุดจากจุดเริ่มต้นไปยังทุกจุดในกราฟ

 

วิเคราะห์ Complexity

- Time Complexity: Bellman-Ford Algorithm มีเวลาในการทำงาน โดยเฉลี่ยเท่ากับ \(O(V \cdot E)\) โดยที่ \(V\) คือจำนวนเวอร์เท็กส์ และ \(E\) คือจำนวนขอบ - Space Complexity: Complexity ในพื้นที่มีค่า \(O(V)\) เพราะเราต้องจัดเก็บค่าระยะทางจากจุดเริ่มต้นไปยังแต่ละจุด

 

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

ข้อดี

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

2. เข้าใจง่ายและสามารถใช้งานได้ไม่ยาก

ข้อเสีย

1. มีความเร็วที่ช้าเมื่อเปรียบเทียบกับ Dijkstra’s Algorithm ในกรณีที่ไม่มีขอบน้ำหนักเชิงลบ

2. ใช้เวลาในการประมวลผลสูงในกราฟที่มีจำนวนขอบมากเกินไป

 

บทสรุป

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

หากคุณต้องการเรียนรู้เพิ่มเติมเกี่ยวกับโปรแกรมมิ่งและการวิเคราะห์ Algorithm ที่ซับซ้อน เราขอเชิญคุณเข้าร่วมหลักสูตรที่ EPT แล้วมาร่วมเป็นส่วนหนึ่งกับเรา มาพัฒนาและสร้างสรรค์สิ่งใหม่ๆ ไปด้วยกัน!

 

 

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