รู้จัก Bellman-Ford Algorithm: การหาทางที่สั้นที่สุดในกราฟ

 

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

 

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

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

 

การใช้งานและ Use Case

การใช้ Bellman-Ford Algorithm สามารถปรับใช้ได้ในหลายๆ สถานการณ์ ตัวอย่างเช่น:

- ระบบการนำน้ำมัน: การค้นหาทางที่สั้นที่สุดในการขนส่งน้ำมันระหว่างแหล่งผลิตและสถานีบริการ - การวางแผนเส้นทางการเดินทาง: ใช้ในการคำนวณเส้นทางที่ดีกว่าในการเดินทางจากจุด A ไปยังจุด B - เครือข่ายการสื่อสาร: การวางแผนเส้นทางของข้อมูลในการส่งข้อมูลในเครือข่ายที่มีค่าความล่าช้าแตกต่างกัน

 

ความซับซ้อน (Time Complexity)

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

 

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

ข้อดี

1. สามารถจัดการกับน้ำหนักเป็นลบ: อัลกอริธึมนี้สามารถหาทางที่สั้นที่สุดแม้จะมีน้ำหนักเป็นลบในกราฟ 2. ตรวจจับวงจรลบ: หากกราฟมีวงจรลบ Bellman-Ford จะสามารถตรวจจับได้ ทำให้เรารู้ว่าเส้นทางที่ดีกว่าจะไม่มีอยู่จริง

ข้อเสีย

1. ประสิทธิภาพต่ำเมื่อเทียบกับ Dijkstra: สำหรับกราฟที่ไม่มีน้ำหนักเป็นลบ อัลกอริธึม Dijkstra จะมีประสิทธิภาพที่ดีกว่า 2. ใช้เวลามาก: ความซับซ้อน O(VE) อาจจะทำให้การประมวลผลช้าลงในกราฟที่ใหญ่

 

ตัวอย่างโค้ดใน Objective-C

ด้านล่างนี้คือโค้ดตัวอย่างการใช้งาน Bellman-Ford Algorithm ในภาษา Objective-C ซึ่งช่วยในการคำนวณเส้นทางที่สั้นที่สุดจากโหนดหนึ่งไปยังอีกโหนดหนึ่ง

 #import <Foundation/Foundation.h>

@interface Edge : NSObject
@property (nonatomic) int source;
@property (nonatomic) int destination;
@property (nonatomic) int weight;
@end

@implementation Edge
@end

@interface Graph : NSObject
@property (nonatomic) int vertexCount;
@property (nonatomic, strong) NSMutableArray<Edge *> *edges;
- (instancetype)initWithVertexCount:(int)vertexCount;
- (void)addEdgeFrom:(int)source to:(int)destination withWeight:(int)weight;
- (void)bellmanFord:(int)startVertex;
@end

@implementation Graph

- (instancetype)initWithVertexCount:(int)vertexCount {
    self = [super init];
    if (self) {
        _vertexCount = vertexCount;
        _edges = [[NSMutableArray alloc] init];
    }
    return self;
}

- (void)addEdgeFrom:(int)source to:(int)destination withWeight:(int)weight {
    Edge *edge = [[Edge alloc] init];
    edge.source = source;
    edge.destination = destination;
    edge.weight = weight;
    [self.edges addObject:edge];
}

- (void)bellmanFord:(int)startVertex {
    int distance[self.vertexCount];

    for (int i = 0; i < self.vertexCount; i++) {
        distance[i] = INT_MAX;
    }
    distance[startVertex] = 0;

    for (int i = 1; i < self.vertexCount; i++) {
        for (Edge *edge in self.edges) {
            if (distance[edge.source] != INT_MAX && distance[edge.source] + edge.weight < distance[edge.destination]) {
                distance[edge.destination] = distance[edge.source] + edge.weight;
            }
        }
    }

    for (Edge *edge in self.edges) {
        if (distance[edge.source] != INT_MAX && distance[edge.source] + edge.weight < distance[edge.destination]) {
            NSLog(@"Graph contains a negative-weight cycle");
            return;
        }
    }

    NSLog(@"Vertex Distance from Source:");
    for (int i = 0; i < self.vertexCount; i++) {
        NSLog(@"%d: %d", i, distance[i]);
    }
}
@end

int main(int argc, const char * argv[]) {
    @autoreleasepool {
        Graph *graph = [[Graph alloc] initWithVertexCount:5];
        [graph addEdgeFrom:0 to:1 withWeight:-1];
        [graph addEdgeFrom:0 to:2 withWeight(4)];
        [graph addEdgeFrom:1 to:2 withWeight(3)];
        [graph addEdgeFrom:1 to:3 withWeight(2)];
        [graph addEdgeFrom:1 to:4 withWeight(2)];
        [graph addEdgeFrom:3 to:1 withWeight(1)];
        [graph addEdgeFrom:3 to:4 withWeight(5)];
        [graph addEdgeFrom:4 to:3 withWeight(-3)];

        [graph bellmanFord:0];
    }
    return 0;
}

 

สรุป

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

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

 

 

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