Bellman-Ford Algorithm: การค้นหาทางที่สั้นที่สุดในกราฟด้วย Delphi Object Pascal

เมื่อเราพูดถึงการค้นหาทางที่สั้นที่สุดในกราฟ หลายคนอาจนึกถึง Dijkstra’s Algorithm แต่ยังมีอีกหนึ่งอัลกอริธึมที่สำคัญไม่น้อยคือ Bellman-Ford Algorithm อัลกอริธึมนี้มีข้อดีในหลายแง่มุม เช่น สามารถทำงานได้กับกราฟที่มีน้ำหนักลบ และสามารถตรวจจับวงจรลบ (negative cycles) ในกราฟได้เช่นกัน ในบทความนี้เราจะมาพูดถึง Bellman-Ford Algorithm โดยเน้นการใช้งานด้วย Delphi Object Pascal

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

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

Use Case ในโลกจริง

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

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

Complexity ของ Bellman-Ford Algorithm คือ O(V * E) โดยที่ V คือจำนวนของเวิร์ทเท็กซ์ (vertices) และ E คือจำนวนของขอบ (edges) ในกราฟ สิ่งนี้ทำให้ Bellman-Ford เป็นทางเลือกที่ดีสำหรับกราฟที่มีขนาดเล็กถึงปานกลาง แต่ไม่ควรใช้สำหรับกราฟขนาดใหญ่เนื่องจากเวลาในการประมวลผลจะสูงขึ้นเรื่อย ๆ

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

ข้อดี:

1. รองรับกราฟที่มีน้ำหนักลบ - Bellman-Ford Algorithm สามารถทำงานได้ในกรณีที่มีขอบที่มีน้ำหนักลบ ซึ่ง Dijkstra จะไม่สามารถทำได้

2. ตรวจจับวงจรลบ - Bellman-Ford สามารถตรวจจับความเป็นไปได้ที่ว่ามีวงจรที่สามารถหาผลลัพธ์ที่เป็นลบได้ ทำให้สามารถป้องกันปัญหาในระบบได้

ข้อเสีย:

1. ประสิทธิภาพต่ำ - โดยเฉพาะกับกราฟที่มีจำนวนขอบ (edges) มาก ๆ เนื่องจากเวลาประมวลผล O(V * E) จึงไม่เหมาะสำหรับกราฟที่มีขนาดใหญ่มาก

2. ไม่เหมาะใช้ในกราฟที่มีลักษณะไม่ระบุความเชื่อมโยงทางข้อมูล - ในกรณีที่ไม่สามารถประเมินได้ว่าขอบจากกันมีน้ำหนักอย่างไร ก็ไม่เหมาะใช้ Bellman-Ford

ตัวอย่าง Code ด้วย Delphi Object Pascal

ด้านล่างนี้เป็นตัวอย่างการใช้งาน Bellman-Ford Algorithm โดยใช้ภาษา Delphi Object Pascal เพื่อหาทางที่สั้นที่สุดจากจุดใช้งานที่กำหนด:

 program BellmanFord;

type
    TEdge = record
        src, dest, weight: Integer;
    end;

const
    MAX_VERTICES = 10;
    INFINITY = 99999;

var
    edges: array[1..MAX_VERTICES] of TEdge;
    dist: array[1..MAX_VERTICES] of Integer;
    V, E, i, j: Integer;

procedure BellmanFord(src: Integer);
var
    i, j: Integer;
begin
    for i := 1 to V do
        dist[i] := INFINITY;

    dist[src] := 0;

    for i := 1 to V - 1 do
    begin
        for j := 1 to E do
        begin
            if (dist[edges[j].src] + edges[j].weight < dist[edges[j].dest]) then
                dist[edges[j].dest] := dist[edges[j].src] + edges[j].weight;
        end;
    end;

    for j := 1 to E do
    begin
        if (dist[edges[j].src] + edges[j].weight < dist[edges[j].dest]) then
            WriteLn('Graph contains negative weight cycle');
    end;
end;

begin
    WriteLn('Enter the number of vertices and edges:');
    ReadLn(V, E);
    WriteLn('Enter edges (src, dest, weight):');

    for i := 1 to E do
        ReadLn(edges[i].src, edges[i].dest, edges[i].weight);

    BellmanFord(1); // Use vertex 1 as starting point

    WriteLn('Vertex Distance from Source');
    for i := 1 to V do
        WriteLn(i, ' : ', dist[i]);
end.

สรุป

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

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

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