Dijkstra Algorithm in C

 

การค้นหาเส้นทางที่สั้นที่สุด (Shortest Path Problem) เป็นหนึ่งในปัญหาพื้นฐานที่พบได้บ่อยในงานวิจัยด้านกราฟและระบบเครือข่าย เช่น การหาเส้นทางในแผนที่หรือโครงข่ายสื่อสาร หนึ่งในอัลกอริทึมที่โดดเด่นที่สามารถแก้ไขปัญหาดังกล่าวได้อย่างมีประสิทธิภาพคือ Dijkstra Algorithm ซึ่งเป็นที่นิยมและใช้งานกันอย่างกว้างขวาง ในบทความนี้เราจะพูดถึงหลักการของอัลกอริทึมนี้, ข้อดีข้อเสีย, จัดการวิเคราะห์ความซับซ้อนของมัน รวมถึงแสดงตัวอย่างโค้ดเพื่อให้เข้าใจง่ายขึ้น มาร่วมสำรวจการทำงานของอัลกอริทึมที่สำคัญนี้กันเถอะ!

 

อัลกอริทึมของ Dijkstra คืออะไร?

Dijkstra Algorithm ตั้งชื่อตามผู้พัฒนา, Edsger W. Dijkstra, สร้างขึ้นเพื่อคำนวณหาเส้นทางที่สั้นที่สุดระหว่างจุดเริ่มต้นและจุดปลายทางในกราฟที่มีน้ำหนักของเส้นเชื่อมระหว่างโหนด (การทำงานของมันจะกำหนดไว้ในกราฟที่มีน้ำหนักไม่เป็นลบเท่านั้น) โดยใช้กลไกของการอัพเดตน้ำหนักเส้นทางและการเลือกเส้นทางที่ดีที่สุดในแต่ละขั้นตอนการวนซ้ำ

 

ตัวอย่างโค้ดและการประยุกต์ใช้งาน

ก่อนที่เราจะไปสู่การแสดงตัวอย่างของโค้ด เราควรทำความเข้าใจคำถามสำคัญว่า "Dijkstra Algorithm เหมาะสำหรับการใช้งานในกรณีใด?" บางตัวอย่างง่ายๆของปัญหาเขาต้องการหาเส้นทางที่สั้นที่สุดได้แก่:

- การหาเส้นทางบนแผนที่สำหรับการนำทาง GPS

- การกำหนดเส้นทางข้อมูลในเครือข่ายคอมพิวเตอร์เพื่อลดเวลาการส่งข้อมูล

- การคำนวณเส้นทางของข้อมูลที่ไหลผ่านระบบไฟเบอร์ออฟติก

- ระบบการจัดส่งสินค้าโลจิสติกส์เพื่อหาเส้นทางที่เหมาะสมที่สุด

- ในเกมประเภทต่างๆสำหรับการคำนวณเส้นทางของ AI

ตัวอย่างโค้ดเพื่อสืบค้นหาเส้นทางที่สั้นที่สุดโดยใช้ Dijkstra Algorithm บนภาษา C

#include 
#include 

#define V 9

int minDistance(int dist[], int sptSet[]) {
    int min = INT_MAX, min_index;

    for (int v = 0; v < V; v++)
        if (sptSet[v] == 0 && dist[v] <= min)
            min = dist[v], min_index = v;
    return min_index;
}

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

void dijkstra(int graph[V][V], int src) {
    int dist[V];
    int sptSet[V];

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

    dist[src] = 0;

    for (int count = 0; count < V - 1; count++) {
        int u = minDistance(dist, sptSet);
        sptSet[u] = 1;

        for (int v = 0; v < V; v++)
            if (!sptSet[v] && graph[u][v] && dist[u] != INT_MAX
                                       && dist[u] + graph[u][v] < dist[v])
                dist[v] = dist[u] + graph[u][v];
    }

    printSolution(dist);
}

int main() {
    int graph[V][V] = { {0, 4, 0, 0, 0, 0, 0, 8, 0},
                          {4, 0, 8, 0, 0, 0, 0, 11, 0},
                          {0, 8, 0, 7, 0, 4, 0, 0, 2},
                          {0, 0, 7, 0, 9, 14, 0, 0, 0},
                          {0, 0, 0, 9, 0, 10, 0, 0, 0},
                          {0, 0, 4, 14, 10, 0, 2, 0, 0},
                          {0, 0, 0, 0, 0, 2, 0, 1, 6},
                          {8, 11, 0, 0, 0, 0, 1, 0, 7},
                          {0, 0, 2, 0, 0, 0, 6, 7, 0} };
    dijkstra(graph, 0);
    return 0;
}

โค้ดข้างต้นแสดงการทำงานของ Dijkstra Algorithm ในการหาเส้นทางที่สั้นที่สุดจากโหนด 0 เป็นจุดเริ่มต้น

 

การวิเคราะห์ความซับซ้อนของ Dijkstra Algorithm

ความซับซ้อนเวลาของอัลกอริทึมนี้ขึ้นอยู่กับการใช้งานข้อมูลโครงสร้าง เช่น หากใช้ array แบบง่ายทั่วไป, ความซับซ้อนจะอยู่ที่ O(V^2) ถ้าใช้ Min Priority Queue มันสามารถลดเหลือ O(V + ElogV) โดยที่ V คือจำนวนของโหนด และ E คือจำนวนของเส้นเชื่อมขอบ

 

ข้อดีและข้อเสียของ Dijkstra Algorithm

ข้อดี:

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

ข้อเสีย:

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

สำหรับใครก็ตามที่สนใจเรียนรู้เพิ่มเติมเกี่ยวกับการหาเส้นทางที่สั้นที่สุดหรือการใช้งานและการแก้ไขปัญหาด้านกราฟหรือเครือข่าย, EPT หรือสถาบันการศึกษาด้านการเขียนโปรแกรมซึ่งเรามีหลักสูตรที่เปี่ยมด้วยคุณภาพสำหรับการพัฒนาทักษะการเขียนโปรแกรม ยินดีต้อนรับนักเรียนทุกท่านที่พร้อมจะก้าวไปด้วยกันในโลกของการเขียนโปรแกรม!

 

 

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