Bellman-Ford Algorithm ในภาษา C#: อลิตธอร์ริทึมที่ตอบโจทย์ความท้าทายของการหาเส้นทางที่สั้นที่สุด

ในโลกของโปรแกรมมิ่ง การหาเส้นทางที่สั้นที่สุด (Shortest Path Problem) เป็นหนึ่งในปริศนาที่นักพัฒนาซอฟต์แวร์และนักวิทยาศาสตร์ข้อมูลต้องเผชิญอยู่เป็นประจำ มีอลิตธอร์ริทึมต่างๆ ถูกคิดค้นขึ้นเพื่อเอาชนะความท้าทายนี้ และหนึ่งในนั้นคือ Bellman-Ford Algorithm ซึ่งเป็นเครื่องมือที่มีความสามารถในการตรวจจับวงจรลบ (Negative Cycles) และหาเส้นทางที่สั้นที่สุดแม้ในกราฟที่มีน้ำหนักเป็นลบก็ตาม

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

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

จุดเด่นของ Bellman-Ford Algorithm

พื้นฐานทางคณิตศาสตร์และ Complexity

Bellman-Ford Algorithm ทำงานโดยการผ่อนคลาย (Relaxation) ขอบของกราฟ |V| - 1 ครั้ง โดยที่ V คือจำนวนของจุดยอดในกราฟ ซึ่งทำให้มีความซับซ้อนของอลิตธอร์ริทึมที่เป็น Big-O ของ O(V*E) ในที่นี้ E คือจำนวนขอบในกราฟ

ตัวอย่าง Code ในภาษา C#

สมมุติว่าเรามีกราฟที่แสดงด้วยการใช้ adjacency list และเราต้องการหาเส้นทางที่สั้นที่สุดจากจุดเริ่มต้นที่กำหนด ต่อไปนี้คือตัวอย่าง code ของ Bellman-Ford Algorithm ในภาษา C#:

public class Edge { public int Source, Destination, Weight; }
public class Graph { public int Vertices; public List Edges; }

public class BellmanFord
{
    public static int[] BellmanFordAlgorithm(Graph graph, int source)
    {
        int vertices = graph.Vertices;
        int[] distances = new int[vertices];
        for (int i = 0; i < vertices; i++) distances[i] = int.MaxValue;
        distances[source] = 0;

        for (int i = 0; i < vertices - 1; i++)
        {
            foreach (Edge edge in graph.Edges)
            {
                int u = edge.Source;
                int v = edge.Destination;
                int weight = edge.Weight;
                if (distances[u] != int.MaxValue && distances[u] + weight < distances[v])
                {
                    distances[v] = distances[u] + weight;
                }
            }
        }

        foreach (Edge edge in graph.Edges)
        {
            int u = edge.Source;
            int v = edge.Destination;
            int weight = edge.Weight;
            if (distances[u] != int.MaxValue && distances[u] + weight < distances[v])
            {
                throw new Exception("Graph contains a negative-weight cycle");
            }
        }

        return distances;
    }
}

ในข้อแปลนี้ เราสร้างโครงสร้างข้อมูลสำหรับการแสดงกราฟและเส้นขอบ และทำประมวลผลอลิตธอร์ริทึมด้วยเมธอด `BellmanFordAlgorithm`.

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