ทำความรู้จักกับ Dijkstra Algorithm ผ่านภาษา Objective-C

 

 

Dijkstra Algorithm คืออะไร?

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

การประยุกต์ใช้ Dijkstra Algorithm

Dijkstra Algorithm มักถูกใช้งานในหลายสถานการณ์ เช่น:

- ระบบนำทาง GPS ที่ต้องการค้นหาเส้นทางที่สั้นที่สุดระหว่างสองจุด

- ระบบเครือข่ายเพื่อหาทางที่ดีที่สุดในขณะที่ส่งข้อมูล

- การวางแผนการขนส่งสินค้าไปยังจุดหมายต่าง ๆ

 

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

เพื่อให้เห็นภาพรวมของการทำงานของ Dijkstra Algorithm ในภาษา Objective-C เรามาดูตัวอย่าง Code ดังต่อไปนี้:

 #import <Foundation/Foundation.h>

@interface Graph : NSObject

@property (nonatomic, strong) NSMutableArray *vertices;
@property (nonatomic, strong) NSMutableDictionary *edges;

- (void)addVertex:(NSString *)vertex;
- (void)addEdgeFrom:(NSString *)from to:(NSString *)to weight:(NSInteger)weight;
- (NSMutableDictionary *)dijkstra:(NSString *)startVertex;

@end

@implementation Graph

- (instancetype)init {
    if (self = [super init]) {
        _vertices = [NSMutableArray array];
        _edges = [NSMutableDictionary dictionary];
    }
    return self;
}

- (void)addVertex:(NSString *)vertex {
    [_vertices addObject:vertex];
    _edges[vertex] = [NSMutableDictionary dictionary];
}

- (void)addEdgeFrom:(NSString *)from to:(NSString *)to weight:(NSInteger)weight {
    _edges[from][to] = @(weight);
}

- (NSMutableDictionary *)dijkstra:(NSString *)startVertex {
    NSMutableDictionary *distances = [NSMutableDictionary dictionary];
    NSMutableSet *visited = [NSMutableSet set];

    for (NSString *vertex in _vertices) {
        distances[vertex] = @(NSIntegerMax);
    }
    distances[startVertex] = @(0);

    while (visited.count < _vertices.count) {
        NSString *currentVertex = nil;

        for (NSString *vertex in _vertices) {
            if (![visited containsObject:vertex]) {
                if (currentVertex == nil || [distances[vertex] integerValue] < [distances[currentVertex] integerValue]) {
                    currentVertex = vertex;
                }
            }
        }

        if (currentVertex == nil) {
            break;
        }

        [visited addObject:currentVertex];

        for (NSString *neighbor in _edges[currentVertex]) {
            NSInteger newDist = [distances[currentVertex] integerValue] + [_edges[currentVertex][neighbor] integerValue];
            if (newDist < [distances[neighbor] integerValue]) {
                distances[neighbor] = @(newDist);
            }
        }
    }

    return distances;
}

@end

int main(int argc, const char * argv[]) {
    @autoreleasepool {
        Graph *graph = [[Graph alloc] init];
        [graph addVertex:@"A"];
        [graph addVertex:@"B"];
        [graph addVertex:@"C"];
        [graph addVertex:@"D"];

        [graph addEdgeFrom:@"A" to:@"B" weight:1];
        [graph addEdgeFrom:@"A" to:@"C" weight:4];
        [graph addEdgeFrom:@"B" to:@"C" weight:2];
        [graph addEdgeFrom:@"B" to:@"D" weight:5];
        [graph addEdgeFrom:@"C" to:@"D" weight:1];

        NSMutableDictionary *shortestPaths = [graph dijkstra:@"A"];

        for (NSString *vertex in shortestPaths) {
            NSLog(@"Distance from A to %@ is %@", vertex, shortestPaths[vertex]);
        }
    }
    return 0;
}

 

การวิเคราะห์ Complexity ของ Dijkstra Algorithm

การวิเคราะห์ Complexity ของ Dijkstra Algorithm มีหลายรูปแบบโดยขึ้นอยู่กับการใช้โครงสร้างข้อมูลในการเก็บระยะทางและการทำงานในแต่ละรอบ:

- Time Complexity: O(V^2) เมื่อใช้ array ในการเก็บค่าระยะทาง ซึ่ง V คือจำนวน vertex หรือจุดที่ต้องพิจารณา - Space Complexity: O(V) เพื่อเก็บค่าระยะทางและข้อมูลที่เกี่ยวข้อง

หากใช้ Min-Heap หรือ Priority Queue ในการค้นหาเส้นทางที่สั้นที่สุด Time Complexity จะถูกปรับปรุงให้เป็น O(E log V) ซึ่ง E คือจำนวน edge

 

ข้อดีข้อเสียของ Dijkstra Algorithm

ข้อดี:

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

ข้อเสีย:

1. ไม่สามารถใช้กับกราฟที่มี edge น้ำหนักเป็นลบ: อัลกอริธึมนี้ไม่สามารถทำงานได้ดีในกราฟที่มีน้ำหนักเชิงลบ 2. ไม่เหมาะสำหรับกราฟขนาดใหญ่: เมื่อกราฟมีขนาดใหญ่มาก การใช้เวลาของอัลกอริธึมจะเพิ่มขึ้นอย่างรวดเร็ว

 

สรุป

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

 

 

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