เข้าใจ Bellman-Ford Algorithm: วิธีการหาค่าสูงสุดในกราฟ

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

Bellman-Ford Algorithm เป็นวิธีการหาค่าทางลัดที่สั้นที่สุดในกราฟที่มีน้ำหนัก (Weighted Graph) ซึ่งสามารถจัดการสถานการณ์ที่มีกราฟที่มีขอบเชิงลบ (Negative Edge) ได้อย่างมีประสิทธิภาพ ในทางเทคนิคมันจะช่วยหาค่าทางที่สั้นที่สุดจากจุดเริ่มต้น (Source Node) ไปยังทุกจุดในกราฟ

ทำไมต้องใช้ Bellman-Ford Algorithm?

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

ตัวอย่างการใช้ Bellman-Ford Algorithm ในโครงการ

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

ตัวอย่างโค้ด Bellman-Ford Algorithm ในภาษา Scala

 import scala.collection.mutable

case class Edge(src: Int, dest: Int, weight: Int)

object BellmanFord {
  def findShortestPath(edges: List[Edge], v: Int, source: Int): List[Int] = {
    val distance = mutable.ArrayBuffer.fill(v)(Int.MaxValue)
    distance(source) = 0

    for (_ <- 1 until v) {
      for (edge <- edges) {
        if (distance(edge.src) != Int.MaxValue && distance(edge.src) + edge.weight < distance(edge.dest)) {
          distance(edge.dest) = distance(edge.src) + edge.weight
        }
      }
    }

    // ตรวจสอบการมีอยู่ของลูปที่เป็นลบ
    for (edge <- edges) {
      if (distance(edge.src) != Int.MaxValue && distance(edge.src) + edge.weight < distance(edge.dest)) {
        println("Graph contains negative weight cycle")
        return List(-1)
      }
    }

    distance.toList
  }

  def main(args: Array[String]): Unit = {
    val edges = List(
      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 v = 5
    val source = 0
    val distances = findShortestPath(edges, v, source)

    println(s"Vertex Distance from Source:$distances")
  }
}

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

Bellman-Ford Algorithm มีความซับซ้อนทางเวลา (Time Complexity) เป็น O(VE) โดยที่ V คือจำนวนจุดยอด (Vertices) และ E คือจำนวนขอบ (Edges) ในกราฟ ผลลัพธ์ที่ได้คือมุมมองในการใช้เวลาในการค้นหาที่แยกออกมาให้กับทุกขอบ ซึ่งเราต้องทำการวนรอบจำนวนครั้งที่เป็นไปตามความยาวของกราฟ

ความซับซ้อนทางพื้นที่ (Space Complexity) จะอยู่ที่ O(V) เนื่องจากเราจะจัดเก็บระยะทางจากจุดเริ่มต้นไปยังจุดอื่น ๆ ในอาร์เรย์

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

ข้อดี

ข้อเสีย

สรุป

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

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

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