รู้จักกับ Dijkstra Algorithm: วิธีการค้นหาความสั้นที่สุดในกราฟด้วย PHP

 

 

แนะนำ Dijkstra Algorithm

Dijkstra Algorithm เป็นอัลกอริธึมที่ใช้ในการค้นหาทางที่สั้นที่สุดระหว่างจุดสองจุดในกราฟที่มีน้ำหนักที่ไม่เป็นลบ อัลกอริธึมนี้ถูกสร้างขึ้นโดย Edsger W. Dijkstra ในปี 1956 โดยเราสามารถใช้งานอัลกอริธึมนี้ได้ในหลาย ๆ สถานการณ์ เช่น การค้นหาเส้นทางที่ดีที่สุดในระบบแผนที่ออนไลน์ การรันโปรแกรมเพื่อวางแผนทรัพยากร เป็นต้น

ใช้แก้ปัญหาอะไร?

Dijkstra Algorithm มักใช้ในสถานการณ์ที่เราต้องการค้นหาทางที่สั้นที่สุดจากจุดต้นทาง (source) ไปยังจุดปลายทาง (destination) ในกราฟ เช่น:

- การค้นหาสถานีขนส่งที่ใกล้ที่สุด

- ระบบนำทาง GPS

- การวางแผนเส้นทางในเกมออนไลน์

- การเชื่อมต่อระหว่างโหนดในโครงสร้างเครือข่ายคอมพิวเตอร์

 

ตัวอย่างโค้ดในภาษา PHP

ต่อไปนี้คือโค้ดตัวอย่างที่แสดงการใช้ Dijkstra Algorithm ในภาษา PHP:

 <?php

function dijkstra($graph, $source) {
    $dist = [];
    $prev = [];
    $queue = [];

    foreach ($graph as $vertex => $edges) {
        $dist[$vertex] = INF;
        $prev[$vertex] = null;
        $queue[$vertex] = INF;
    }

    $dist[$source] = 0;
    $queue[$source] = 0;

    while (!empty($queue)) {
        asort($queue);
        $currentVertex = key($queue);
        unset($queue[$currentVertex]);

        foreach ($graph[$currentVertex] as $neighbor => $weight) {
            $alt = $dist[$currentVertex] + $weight;

            if ($alt < $dist[$neighbor]) {
                $dist[$neighbor] = $alt;
                $prev[$neighbor] = $currentVertex;
                $queue[$neighbor] = $alt;
            }
        }
    }

    return [$dist, $prev];
}

// ตัวอย่างกราฟ
$graph = [
    'A' => ['B' => 1, 'C' => 4],
    'B' => ['A' => 1, 'C' => 2, 'D' => 5],
    'C' => ['A' => 4, 'B' => 2, 'D' => 1],
    'D' => ['B' => 5, 'C' => 1],
];

// เรียกใช้ฟังก์ชัน
list($dist, $prev) = dijkstra($graph, 'A');
print_r($dist);
print_r($prev);
?>

อธิบายโค้ด

ในโค้ดข้างต้น:

1. ฟังก์ชัน dijkstra จะรับพารามิเตอร์เป็นกราฟ (ซึ่งนิยามเป็นอาร์เรย์ที่ประกอบด้วยโหนดและน้ำหนักของขอบที่เชื่อมโยง) และจุดเริ่มต้น (source) ที่เราต้องการหาทางที่สั้นที่สุด

2. เราสร้างตัวแปร `$dist` เพื่อเก็บระยะห่างจากจุดเริ่มต้นไปยังทุกจุด และ `$prev` เพื่อเก็บแหล่งที่มาของเส้นทางที่สั้นที่สุด

3. ลูปหลักจะทำงานจนกว่าเงื่อนไขของคิวจะหมด โดยจะหาค่าที่น้อยที่สุดและปรับค่า `$dist` และ `$prev` อย่างเหมาะสม

4. ในที่สุด ฟังก์ชันจะคืนค่าระยะทางและเส้นทางก่อนหน้า

 

Use Case ในโลกจริง

การกำหนดเส้นทางในรถยนต์:

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

 

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

Dijkstra Algorithm มีความซับซ้อนเชิงเวลา (Time Complexity) ที่ขึ้นอยู่กับวิธีการในการจัดการคิว โดยทั่วไปแล้วถ้าเราต้องการใช้โครงสร้างข้อมูลแบบ Min Heap จะมีความซับซ้อนที่ O(E log V) โดยที่ V คือจำนวนโหนด และ E คือจำนวนขอบ (edges) แต่ถ้าใช้ลิสต์เชื่อมโยง (adjacency list) จะมีความซับซ้อน O(V^2).

 

ข้อดีและข้อเสียของ Algorithm นี้

ข้อดี

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

ข้อเสีย

1. กรณีน้ำหนักลบ: ไม่สามารถใช้ได้ในกราฟที่มีน้ำหนักของขอบเป็นลบ 2. ใช้หน่วยความจำสูง: ในกรณีของกราฟที่มีขนาดใหญ่ การจัดการหน่วยความจำอาจจะท้าทาย 3. ใช้เวลา: ในบางสถานการณ์ อาจจะใช้เวลานานในการค้นหาทางที่สั้นที่สุด

 

บทสรุป

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

 

 

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