สำรวจความลึกลับของ Bellman-Ford Algorithm ด้วยภาษา C

ในโลกของการเขียนโปรแกรม เรามักจะพบกับปัญหาต่างๆ ที่ต้องการคำตอบหรือวิธีการแก้ปัญหาที่ชาญฉลาด Bellman-Ford Algorithm คือหนึ่งในเครื่องมือที่ช่วยแก้ไขปัญหาสำคัญของโครงข่าย นั่นก็คือ "การหาเส้นทางที่สั้นที่สุด" แต่เมื่อเราหลุดพ้นจากแบบแผนของการหาเส้นทางที่สั้นที่สุดด้วย Dijkstra Algorithm ที่ให้คำตอบเมื่อเส้นทางความยาวเป็นบวกเสมอ Bellman-Ford ก้าวเข้ามาด้วยความสามารถที่จะหาเส้นทางที่สั้นที่สุดได้แม้ในกรณีที่น้ำหนักของเส้นทางมีค่าเป็นลบ ซึ่งเป็นข้อดีใหญ่หลวงของมันเลยทีเดียว อย่างไรก็ตาม ความสามารถนี้กลับเป็นจุดอ่อนในทางหนึ่ง เพราะมันเปิดโอกาสให้เกิด 'negative cycles' หรือวัฏจักรที่มีน้ำหนักเป็นลบซึ่งอาจทำให้การคำนวณไม่มีวันสิ้นสุด

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

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

ตัวอย่างโค้ดภาษา C ที่ใช้ Bellman-Ford Algorithm:

#include
#include
#include

struct Edge {
   int src, dest, weight;
};

struct Graph {
   int V, E;
   struct Edge* edge;
};

struct Graph* createGraph(int V, int E) {
   struct Graph* graph = (struct Graph*) malloc(sizeof(struct Graph));
   graph->V = V;
   graph->E = E;
   graph->edge = (struct Edge*) malloc(graph->E * sizeof(struct Edge));
   return graph;
}

void printArr(int dist[], int n) {
   printf("Vertex   Distance from Source\n");
   for (int i = 0; i < n; ++i)
      printf("%d \t\t %d\n", i, dist[i]);
}

void BellmanFord(struct Graph* graph, int src) {
   int V = graph->V;
   int E = graph->E;
   int dist[V];

   for (int i = 0; i < V; i++)
      dist[i] = INT_MAX;
   dist[src] = 0;

   for (int i = 1; i <= V-1; i++) {
      for (int j = 0; j < E; j++) {
         int u = graph->edge[j].src;
         int v = graph->edge[j].dest;
         int weight = graph->edge[j].weight;
         if (dist[u] != INT_MAX && dist[u] + weight < dist[v])
            dist[v] = dist[u] + weight;
      }
   }

   for (int i = 0; i < E; i++) {
      int u = graph->edge[i].src;
      int v = graph->edge[i].dest;
      int weight = graph->edge[i].weight;
      if (dist[u] != INT_MAX && dist[u] + weight < dist[v]) {
         printf("Graph contains negative weight cycle");
         return;
      }
   }

   printArr(dist, V);
   return;
}

// ส่วนของ main function
int main() {
   int V = 5;
   int E = 8;
   struct Graph* graph = createGraph(V, E);

   // ด้านล่างนี้เป็นตัวอย่างการเพิ่มข้อมูลเส้นทางในกราฟ
   // การเพิ่มข้อมูลอย่างเต็มรูปแบบจะขึ้นกับ use-case และกราฟที่จะทำการทดสอบ

   graph->edge[0].src = 0;
   graph->edge[0].dest = 1;
   graph->edge[0].weight = -1;

   graph->edge[1].src = 0;
   graph->edge[1].dest = 2;
   graph->edge[1].weight = 4;

   // ... เพิ่ม edge ต่างๆ ...

   BellmanFord(graph, 0);

   return 0;
}

จากโค้ดด้านบน เราจะเห็นว่าฟังก์ชัน `BellmanFord()` นั้นทำงานโดยการเริ่มจากการตั้งค่าระยะห่างจาก source หรือโหนดเริ่มต้นไปยังทุกโหนดให้เป็น infinity ยกเว้นโหนดต้นทางที่มีระยะห่างเป็น 0 เมื่อสร้างข้อมูลกราฟและรันฟังก์ชันนี้ ก็จะเห็นค่าความยาวที่สั้นที่สุดจากโหนดต้นทางไปยังทุกโหนดทำให้เราสามารถวิเคราะห์ เส้นทางได้บนระบบที่มีความซับซ้อนมากขึ้น

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

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