Dijkstra Algorithm: การค้นหาเส้นทางที่สั้นที่สุดในกราฟด้วยภาษา Dart

 

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

 

Dijkstra Algorithm คืออะไร?

Dijkstra’s Algorithm ได้รับการพัฒนาโดย Edsger Dijkstra ในปี 1956 ซึ่งในปัจจุบันถือเป็นตัวอย่างคลาสสิกในสาขาคณิตศาสตร์และวิทยาการคอมพิวเตอร์ โดยเฉพาะในด้านการค้นหาทางในกราฟ อัลกอริธึมนี้สามารถใช้ในการหาทางสั้นที่สุดจากจุดเริ่มต้น (source) ไปยังจุดปลาย (destination) ในกราฟซึ่งมีน้ำหนักหรือค่าความยาวที่ไม่เป็นลบ

วิธีการทำงาน

1. กำหนดให้ทุกจุดหรือโหนดในกราฟมีค่าน้ำหนักเริ่มต้นเป็นอนันต์ (Infinity) ยกเว้นจุดเริ่มต้นที่จะมีค่าน้ำหนักเป็น 0

2. สร้างโครงสร้างข้อมูลที่มีจุดที่ยังไม่ได้ถูกประมวลผล

3. เลือกโหนดที่มีค่าน้ำหนักต่ำสุดจากโหนดที่อยู่ในลิสต์

4. ทำการปรับปรุงน้ำหนักของโหนดที่เชื่อมต่อกับโหนดที่ถูกเลือก โดยการคำนวณน้ำหนักใหม่ หากน้ำหนักใหม่ต่ำกว่าค่าน้ำหนักเดิมให้ทำการอัพเดท

5. ทำซ้ำกระบวนการนี้จนกว่าจะครบทุกโหนด

 

ตัวอย่างโค้ดในภาษา Dart

เรามาสร้างตัวอย่างโค้ดที่แสดงการทำงานของ Dijkstra Algorithm กับกราฟแบบง่ายกันค่ะ:

 import 'dart:collection';

class Graph {
  final Map<String, Map<String, int>> adjacencyList;

  Graph() : adjacencyList = {};

  void addEdge(String source, String destination, int weight) {
    adjacencyList.putIfAbsent(source, () => {});
    adjacencyList[source]![destination] = weight;
  }

  Map<String, int> dijkstra(String start) {
    Map<String, int> distances = {};
    Set<String> visited = {};
    PriorityQueue<MapEntry<String, int>> priorityQueue = PriorityQueue((a, b) => a.value.compareTo(b.value));

    for (var node in adjacencyList.keys) {
      distances[node] = double.infinity.toInt();
    }

    distances[start] = 0;
    priorityQueue.add(MapEntry(start, 0));

    while (priorityQueue.isNotEmpty) {
      var currentNode = priorityQueue.removeFirst().key;

      if (visited.contains(currentNode)) continue;
      visited.add(currentNode);

      for (var neighbor in adjacencyList[currentNode]!.keys) {
        int weight = adjacencyList[currentNode]![neighbor]!;
        int newDistance = distances[currentNode]! + weight;

        if (newDistance < distances[neighbor]!) {
          distances[neighbor] = newDistance;
          priorityQueue.add(MapEntry(neighbor, newDistance));
        }
      }
    }

    return distances;
  }
}

void main() {
  var graph = Graph();
  graph.addEdge('A', 'B', 1);
  graph.addEdge('A', 'C', 4);
  graph.addEdge('B', 'C', 2);
  graph.addEdge('C', 'D', 1);
  graph.addEdge('B', 'D', 5);

  var shortestPath = graph.dijkstra('A');
  print(shortestPath); // {'A': 0, 'B': 1, 'C': 3, 'D': 4}
}

อธิบายโค้ด

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

 

Use Cases ในโลกจริง

Dijkstra’s Algorithm มีการใช้งานอย่างแพร่หลายในหลายสาขา เช่น:

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

 

วิเคราะห์ Complexity

- Time Complexity: O(E log V) โดยที่ E คือจำนวนขอบในกราฟ และ V คือจำนวนโหนด เนื่องจากมีการใช้ Priority Queue ในการจัดการกับโหนด - Space Complexity: O(V) เนื่องจากพื้นที่ที่ใช้ในการเก็บค่าผลลัพธ์น้ำหนักและโหนดที่ถูกเยี่ยมชม

 

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

ข้อดี

- สามารถหาทางที่สั้นที่สุดจากโหนดเริ่มต้นไปยังทุกโหนดในกราฟได้

- ทำงานได้อย่างมีประสิทธิภาพในกราฟที่มีน้ำหนักเป็นบวก

ข้อเสีย

- ไม่สามารถใช้กับกราฟที่มีค่าลบ เนื่องจากอาจทำให้ผลลัพธ์ไม่ถูกต้อง

- มีความซับซ้อนกับกราฟขนาดใหญ่และน้ำหนักสูง

 

สรุป

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

 

 

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