ค้นหาเส้นทางระยะทางสั้นที่สุดด้วย Dijkstra Algorithm

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

อัลกอริทึมของไดจ์สตร้าคืออะไร?

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

วิธีการทำงานของอัลกอริทึม

อัลกอริทึมของไดจ์สตร้าทำงานตามขั้นตอนดังนี้:

1. เริ่มต้นด้วยการตั้งระยะทางจากจุดต้นทางไปยังจุดที่เหลือเป็นอนันต์ (ยกเว้นจุดต้นทางซึ่งมีระยะทางเป็น 0) และเซตจุดที่เยี่ยมชมแล้วเป็นว่าง

2. เลือกจุดที่มีระยะทางขั้นต่ำที่สุดจากเซตของจุดที่ยังไม่ได้เยี่ยมและที่ไม่ได้อยู่ในเซตของจุดที่เยี่ยมแล้ว

3. อัพเดทระยะทางของเพื่อนบ้านที่เชื่อมโยงกับจุดที่เลือกในขั้นตอนที่ 2 หากพบว่าการอัพเดทจะทำให้ระยะทางเข้าไปยังเพื่อนบ้านนั้นน้อยลง

4. ทำซ้ำขั้นตอนที่ 2 และ 3 จนกระทั่งทุกจุดได้เยี่ยมชมหรือการอัพเดทระยะทางไม่เกิดขึ้นอีก

ตัวอย่างโค้ด Dijkstra Algorithm ในภาษา C++

#include 
#include 
#include 
#include 

using namespace std;

void dijkstra(vector>& graph, int src) {
    int V = graph.size();
    vector dist(V, INT_MAX);
    dist[src] = 0;
    set> setds;

    setds.insert(make_pair(0, src));

    while (!setds.empty()) {
        pair tmp = *(setds.begin());
        setds.erase(setds.begin());
        int u = tmp.second;

        for (int i = 0; i < V; ++i) {
            if (graph[u][i] && dist[i] > dist[u] + graph[u][i]) {
                if (dist[i] != INT_MAX) {
                    setds.erase(setds.find(make_pair(dist[i], i)));
                }
                dist[i] = dist[u] + graph[u][i];
                setds.insert(make_pair(dist[i], i));
            }
        }
    }

    cout << "Vertex Distance from Source\n";
    for (int i = 0; i < V; ++i) {
        cout << i << "\t\t" << dist[i] << endl;
    }
}

int main() {
    vector> graph = {
        {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;
}

ในโค้ดด้านบน เราได้ออกแบบกราฟที่เป็นเมทริกซ์ที่มีขนาด `V x V` พร้อมน้ำหนักในแต่ละเอดจ์ หลังจากนั้น เราจะเรียกใช้ฟังก์ชั่น `dijkstra()` สำหรับหาเส้นทางที่สั้นที่สุดจากจุดเริ่มต้น (จุดที่ 0 ในกรณีนี้) ไปยังจุดอื่นๆ ในกราฟ

ใช้งานในโลกจริง

ในชีวิตจริง, Dijkstra Algorithm สามารถใช้งานได้อย่างกว้างขวาง เช่น ในระบบการนำทาง GPS เพื่อค้นหาเส้นทางที่สั้นที่สุดจากจุด A ไปยังจุด B หรือในโครงข่ายการสื่อสาร เพื่อหาเส้นทางส่งสัญญาณที่ใช้ทรัพยากรน้อยที่สุด

Complexity ของอัลกอริทึม

Dijkstra Algorithm มีความซับซ้อนในเชิงเวลาการทำงานที่ O(V^2) โดย V คือจำนวนจุดในกราฟ หากใช้ min-priority queue จะลดความซับซ้อนลงไปได้อีกเป็น O((V+E)logV) โดย E คือจำนวนเอดจ์

ข้อดีและข้อเสีย

ข้อดี:

- ง่ายต่อการเข้าใจและการลงโปรแกรม

- ค่อนข้างมีประสิทธิภาพในกราฟที่มีขนาดไม่ใหญ่เกินไป

ข้อเสีย:

- ไม่สามารถใช้ได้กับกราฟที่มีน้ำหนักเป็นลบเนื่องจากจะทำให้อัลกอริทึมไม่ถูกต้อง

- อาจจะไม่มีประสิทธิภาพที่สุดสำหรับกราฟที่มีขนาดใหญ่มากหรือในกรณีที่ต้องการหาเส้นทางระหว่างทุกคู่ของจุด

ในขณะที่ Dijkstra Algorithm มีขอบเขตการใช้งานที่จำกัด แต่ก็ยังเป็นหนึ่งในองค์ประกอบสำคัญในทฤษฎีกราฟและการแก้ไขปัญหาในโลกเชิงปฏิบัติ

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

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