แนะนำ Bellman-Ford Algorithm ด้วยภาษา PHP

 

 

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

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

 

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

การค้นหาทางที่สั้นที่สุดในกราฟเป็นปัญหาที่พบเจอได้บ่อยในหลายๆ แอพพลิเคชัน เช่น:

- ระบบนำทาง GPS

- การวางแผนเส้นทางในระบบขนส่งสาธารณะ

- การจัดการเครือข่ายคอมพิวเตอร์

 

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

มาดูตัวอย่างการใช้ Bellman-Ford Algorithm ในโลกจริง เช่น การค้นหาเส้นทางที่ดีที่สุดจากเมือง A ไปยังเมือง D โดยมีสถานที่ต่างๆ ได้แก่ A, B, C, D มีน้ำหนักขอบดังนี้:

- A -> B: 4

- A -> C: 2

- B -> C: 5

- B -> D: 10

- C -> D: 3

 

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

เพื่อให้เข้าใจการทำงานของอัลกอริธึมนี้อย่างชัดเจน ลองมาดูโค้ด PHP ที่ใช้ Bellman-Ford Algorithm กัน:

 <?php

class Edge {
    public $src, $dest, $weight;

    function __construct($src, $dest, $weight) {
        $this->src = $src;
        $this->dest = $dest;
        $this->weight = $weight;
    }
}

function bellmanFord($graph, $V, $E, $start) {
    // Step 1: Initialize distances from start to all other vertices as infinite
    $dist = array_fill(0, $V, PHP_INT_MAX);
    $dist[$start] = 0;

    // Step 2: Relax all edges |V| - 1 times
    for ($i = 0; $i < $V - 1; $i++) {
        foreach ($graph as $edge) {
            if ($dist[$edge->src] !== PHP_INT_MAX &&
                $dist[$edge->src] + $edge->weight < $dist[$edge->dest]) {
                $dist[$edge->dest] = $dist[$edge->src] + $edge->weight;
            }
        }
    }

    // Step 3: Check for negative-weight cycles
    foreach ($graph as $edge) {
        if ($dist[$edge->src] !== PHP_INT_MAX &&
            $dist[$edge->src] + $edge->weight < $dist[$edge->dest]) {
            echo "Graph contains negative weight cycle\n";
            return;
        }
    }

    // Print all distances
    for ($i = 0; $i < $V; $i++) {
        echo "Vertex $i: " . ($dist[$i] == PHP_INT_MAX ? "INFINITY" : $dist[$i]) . "\n";
    }
}

// Create graph
$graph = [];
$graph[] = new Edge(0, 1, 4);
$graph[] = new Edge(0, 2, 2);
$graph[] = new Edge(1, 2, 5);
$graph[] = new Edge(1, 3, 10);
$graph[] = new Edge(2, 3, 3);

// Number of vertices
$V = 4; // 도시 수
$E = count($graph); // 엣지 수

// Invoke the bellmanFord function
bellmanFord($graph, $V, $E, 0);

?>

อธิบายโค้ด

1. การสร้าง Edge class: คคลาสนี้เก็บข้อมูลเกี่ยวกับขอบของกราฟ (src, dest, weight) ทำให้เราสามารถจัดการกับอัลกอริธึมได้ง่าย 2. ฟังก์ชัน bellmanFord: ทำการค้นหาทางที่สั้นที่สุดจากจุดเริ่มต้นไปยังทุกจุดในกราฟ ใช้การทำซ้ำ (Loop) ผ่านขอบของกราฟ และประเมินระยะทางที่สั้นที่สุด 3. การตรวจสอบวงจรลบ: หลังจากทำการ Relax edges เสร็จสิ้น จะมีการตรวจสอบว่ากราฟมีวงจรที่มีน้ำหนักติดลบหรือไม่ 4. แสดงผล: สุดท้ายจะแสดงระยะทางที่สั้นที่สุดไปยังจุดหมายต่างๆ

 

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

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

 

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

ข้อดี

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

2. ง่ายต่อการนำไปใช้งานในแบบจำลองที่ซับซ้อน

3. สามารถตรวจจับวงจรลบได้

ข้อเสีย

1. ช้าเมื่อเทียบกับ Dijkstra’s algorithm หากกราฟไม่มีค่าติดลบ

2. ต้องการการวนลูปที่มากขึ้นเมื่อมีจำนวน vertices สูง

 

สรุป

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

หากคุณต้องการเรียนรู้เพิ่มเติมเกี่ยวกับการเขียนโปรแกรมและอัลกอริธึมต่าง ๆ อย่าลืมเข้ามาที่ EPT (Expert-Programming-Tutor) เพื่อพัฒนาทักษะของคุณ!

 

 

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