เครื่องคำนวณเส้นทางสั้นสุดของไดค์สตรา

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

อัลกอริทึมของไดค์สตราคืออัลกอริทึมการค้นหาในกราฟที่ค้นหาเส้นทางที่สั้นที่สุดจากโหนดต้นทางไปยังโหนดอื่นๆ ทั้งหมดในกราฟที่มีน้ำหนักขอบไม่เป็นลบ โดยใช้กลยุทธ์ Greedy ร่วมกับคิวลำดับความสำคัญ (min-heap) โดยจะประมวลผลโหนดที่ยังไม่ได้เยี่ยมชมที่มีระยะทางสั้นที่สุดที่ทราบเสมอ ความซับซ้อนของเวลาคือ O((V + E) log V) เมื่อใช้ binary heap

Q: อัลกอริทึมของไดค์สตราสามารถจัดการกับน้ำหนักขอบที่เป็นลบได้หรือไม่?

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

Q: กราฟแบบมีทิศทางและไม่มีทิศทางแตกต่างกันอย่างไร?

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

Q: การผ่อนคลายขอบ (Edge relaxation) ในอัลกอริทึมของไดค์สตราคืออะไร?

การผ่อนคลายขอบคือการทำงานหลักในอัลกอริทึมของไดค์สตรา เมื่อเยี่ยมชมโหนด u สำหรับเพื่อนบ้าน v แต่ละโหนด อัลกอริทึมจะตรวจสอบว่าเส้นทางผ่าน u (dist[u] + weight(u,v)) สั้นกว่าระยะทางที่ทราบในปัจจุบันไปยัง v (dist[v]) หรือไม่ หากสั้นกว่า ระยะทางจะถูกอัปเดต (ผ่อนคลาย) และ v จะถูกเพิ่มเข้าไปในคิวลำดับความสำคัญด้วยระยะทางใหม่

Q: ต้นไม้เส้นทางที่สั้นที่สุด (Shortest path tree) คืออะไร?

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

Q: การประยุกต์ใช้อัลกอริทึมของไดค์สตราในโลกแห่งความเป็นจริงมีอะไรบ้าง?

อัลกอริทึมของไดค์สตราถูกใช้ในระบบนำทาง GPS, โปรโตคอลการกำหนดเส้นทางเครือข่าย (OSPF, IS-IS), การวิเคราะห์เครือข่ายสังคม, การเพิ่มประสิทธิภาพเส้นทางสายการบิน, การวางแผนเส้นทางหุ่นยนต์, การค้นหาเส้นทาง AI ในเกม, โลจิสติกส์โซ่อุปทาน และการออกแบบเครือข่ายโทรคมนาคม ปัญหาใดๆ ที่สามารถจำลองเป็นการค้นหาเส้นทางที่สั้นที่สุดหรือประหยัดที่สุดในกราฟจะได้รับประโยชน์จากอัลกอริทึมนี้

ค้นหาเส้นทางที่สั้นที่สุดระหว่างโหนดในกราฟแบบถ่วงน้ำหนักโดยใช้อัลกอริทึมของไดค์สตรา มาพร้อมคุณสมบัติการแสดงภาพกราฟแบบโต้ตอบ การติดตามลำดับความสำคัญของคิวทีละขั้นตอน และการแสดงแผนภาพต้นไม้เส้นทางสั้นสุด

เครื่องคำนวณเส้นทางสั้นสุดของไดค์สตรา

ลองใช้กราฟตัวอย่างเหล่านี้:

เครือข่ายพื้นฐาน เครือข่ายขนาดใหญ่ แบบมีทิศทาง (CLRS) รูปหกเหลี่ยม

ขอบของกราฟ

โหนดต้นทาง

ประเภทกราฟ

รูปแบบ: ต้นทาง, ปลายทาง, น้ำหนัก — หนึ่งขอบต่อหนึ่งบรรทัด ชื่อโหนดสามารถเป็นตัวอักษร ตัวเลข หรือคำก็ได้ น้ำหนักทั้งหมดต้องไม่เป็นลบ

Embed เครื่องคำนวณเส้นทางสั้นสุดของไดค์สตรา Widget

เกี่ยวกับ เครื่องคำนวณเส้นทางสั้นสุดของไดค์สตรา

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

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

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

อัลกอริทึมทำงานโดยการรักษาชุดของโหนดที่ยังไม่ได้เยี่ยมชม และเลือกโหนดที่ยังไม่ได้เยี่ยมชมซึ่งมีระยะทางทดลองน้อยที่สุดซ้ำๆ (กลยุทธ์แบบ Greedy) นี่คือสิ่งที่ทำให้มันทั้งสง่างามและมีประสิทธิภาพ — เมื่อโหนดถูก \"เยี่ยมชม\" แล้ว ระยะทางที่สั้นที่สุดของโหนดนั้นจะได้รับการรับรองว่าเป็นที่สิ้นสุด

รหัสเทียม (Pseudocode) ของอัลกอริทึม

function Dijkstra(Graph, source):
  for each node v in Graph:
    dist[v] ← ∞
    prev[v] ← undefined
  dist[source] ← 0
  Q ← priority queue of all nodes

  while Q is not empty:
    u ← node in Q with minimum dist[u]
    remove u from Q

    for each neighbor v of u still in Q:
      alt ← dist[u] + weight(u, v)
      if alt < dist[v]:
        dist[v] ← alt // การผ่อนคลาย (relaxation)
        prev[v] ← u

  return dist[], prev[]

สูตรหลัก

เงื่อนไขการผ่อนคลายขอบ (Edge Relaxation Condition)

$$\text{if } d[u] + w(u, v) < d[v] \text{ then } d[v] \leftarrow d[u] + w(u, v)$$

โดยที่:

d[u] = ระยะทางที่สั้นที่สุดที่ทราบในปัจจุบันจากต้นทางไปยังโหนด u
w(u, v) = น้ำหนักของขอบจาก u ไปยัง v
d[v] = ระยะทางที่สั้นที่สุดที่ทราบในปัจจุบันจากต้นทางไปยังโหนด v

วิธีใช้งานเครื่องคำนวณนี้

กำหนดขอบกราฟของคุณ: ป้อนขอบในรูปแบบ ต้นทาง, ปลายทาง, น้ำหนัก หนึ่งรายการต่อบรรทัด แต่ละบรรทัดแสดงถึงการเชื่อมต่อระหว่างสองโหนด
เลือกประเภทกราฟ: เลือก \"ไม่มีทิศทาง\" สำหรับขอบสองทาง (เช่น ถนน) หรือ \"มีทิศทาง\" สำหรับขอบทางเดียว (เช่น เส้นทางการบินหรือลิงก์เว็บ)
ตั้งค่าโหนดต้นทาง: ป้อนโหนดเริ่มต้นที่จะใช้คำนวณเส้นทางสั้นสุดทั้งหมด
ค้นหาเส้นทางสั้นสุด: คลิกปุ่มเพื่อเรียกใช้อัลกอริทึมไดค์สตรา สำรวจภาพกราฟแบบโต้ตอบ ตารางระยะทาง และการติดตามทีละขั้นตอน
ดูขั้นตอนการทำงาน: ใช้ปุ่ม ถัดไป/ก่อนหน้า เพื่อดูอัลกอริทึมทำงานทีละขั้นตอน โดยมีการไฮไลต์โหนดและขอบที่อัปเดตในกราฟแบบเรียลไทม์

ทำความเข้าใจผลลัพธ์

ตารางระยะทาง

แสดงระยะทางที่สั้นที่สุดจากต้นทางไปยังทุกโหนด พร้อมกับเส้นทางที่สมบูรณ์ โหนดที่ทำเครื่องหมาย ∞ คือโหนดที่ไม่สามารถเข้าถึงได้จากต้นทาง

การแสดงภาพกราฟ

แคนวาสแบบโต้ตอบจะแสดงกราฟของคุณด้วยโหนดและขอบที่ใช้รหัสสี:

โหนดสีฟ้า = โหนดต้นทาง
โหนดสีเขียว = เยี่ยมชมแล้ว (สรุปผลระยะทางแล้ว)
โหนดสีส้ม = กำลังประมวลผล
โหนดสีเทา = ยังไม่ได้เยี่ยมชม
ขอบสีเขียว = ต้นไม้เส้นทางที่สั้นที่สุด (Shortest path tree)

การติดตามทีละขั้นตอน

แสดงการทำงานของอัลกอริทึม รวมถึงการดึงข้อมูลจากคิวลำดับความสำคัญ การผ่อนคลายขอบ และการอัปเดตระยะทางในแต่ละขั้นตอน สิ่งนี้มีค่ามากสำหรับการเรียนรู้วิธีการทำงานของอัลกอริทึม

ความซับซ้อนของเวลา (Time Complexity)

ประสิทธิภาพของอัลกอริทึมของไดค์สตราขึ้นอยู่กับโครงสร้างข้อมูลที่ใช้สำหรับคิวลำดับความสำคัญ:

Priority Queue	ความซับซ้อนของเวลา	เหมาะสำหรับ
Binary Heap	$ O((V + E) \log V) $	ใช้งานทั่วไป, กราฟแบบเบาบาง (sparse graphs)
Fibonacci Heap	$ O(V \log V + E) $	กราฟแบบหนาแน่น (dense graphs) (ในทางทฤษฎี)
Array (no heap)	$ O(V^2) $	กราฟที่หนาแน่นมาก, จำนวน V น้อย

โดยที่ V คือจำนวนจุดยอด (nodes) และ E คือจำนวนขอบ (edges) เครื่องคำนวณนี้ใช้การทำงานแบบ binary heap

กราฟแบบมีทิศทางเทียบกับไม่มีทิศทาง

กราฟแบบไม่มีทิศทาง: ขอบระหว่าง A และ B หมายความว่าคุณสามารถเดินทางได้ทั้ง A→B และ B→A ตัวอย่าง: เครือข่ายถนน, เครือข่ายมิตรภาพ, วงจรไฟฟ้า
กราฟแบบมีทิศทาง: ขอบจาก A ไป B อนุญาตให้เดินทางจาก A→B เท่านั้น ไม่จำเป็นต้องมี B→A ตัวอย่าง: ไฮเปอร์ลิงก์เว็บ, ผู้ติดตาม Twitter, เส้นทางการบิน, การไหลของแม่น้ำ

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

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

การประยุกต์ใช้ในโลกแห่งความเป็นจริง

การนำทาง GPS

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

การกำหนดเส้นทางเครือข่าย

โปรโตคอลการกำหนดเส้นทางอินเทอร์เน็ต เช่น OSPF (Open Shortest Path First) และ IS-IS ใช้อัลกอริทึมของไดค์สตราเพื่อคำนวณเส้นทางที่สั้นที่สุดผ่านโทโพโลยีเครือข่าย เราเตอร์แต่ละตัวจะสร้างต้นไม้เส้นทางที่สั้นที่สุดเพื่อกำหนดการส่งต่อแพ็กเก็ต

การวิเคราะห์เครือข่ายสังคม

การค้นหาเส้นทางการเชื่อมต่อที่สั้นที่สุดระหว่างผู้ใช้ (องศาของการแยกตัว), การคำนวณการวัดความเป็นศูนย์กลาง และการระบุโหนดที่มีอิทธิพลในเครือข่าย

การพัฒนาเกม

การค้นหาเส้นทางของ NPC ในวิดีโอเกมใช้อัลกอริทึมของไดค์สตราหรือ A* (ซึ่งขยายไดค์สตราด้วย heuristics) เพื่อนำทางในแผนที่เกมและค้นหาเส้นทางการเคลื่อนที่ที่เหมาะสมที่สุด

โซ่อุปทานและโลจิสติกส์

การเพิ่มประสิทธิภาพเส้นทางการจัดส่ง เส้นทางจากคลังสินค้าไปยังร้านค้า และเครือข่ายการขนส่งหลายรูปแบบที่มีค่าใช้จ่ายในการขนส่งแตกต่างกัน

คำถามที่พบบ่อย

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

อัลกอริทึมของไดค์สตราคืออัลกอริทึมการค้นหาในกราฟที่ค้นหาเส้นทางที่สั้นที่สุดจากโหนดต้นทางไปยังโหนดอื่นๆ ทั้งหมดในกราฟที่มีน้ำหนักขอบไม่เป็นลบ โดยใช้กลยุทธ์ Greedy ร่วมกับคิวลำดับความสำคัญ (min-heap) โดยจะประมวลผลโหนดที่ยังไม่ได้เยี่ยมชมที่มีระยะทางสั้นที่สุดที่ทราบเสมอ ความซับซ้อนของเวลาคือ O((V + E) log V) เมื่อใช้ binary heap

อัลกอริทึมของไดค์สตราสามารถจัดการกับน้ำหนักขอบที่เป็นลบได้หรือไม่?

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

กราฟแบบมีทิศทางและไม่มีทิศทางแตกต่างกันอย่างไร?

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

การผ่อนคลายขอบ (Edge relaxation) ในอัลกอริทึมของไดค์สตราคืออะไร?

การผ่อนคลายขอบคือการทำงานหลักในอัลกอริทึมของไดค์สตรา เมื่อเยี่ยมชมโหนด u สำหรับเพื่อนบ้าน v แต่ละโหนด อัลกอริทึมจะตรวจสอบว่าเส้นทางผ่าน u (dist[u] + weight(u,v)) สั้นกว่าระยะทางที่ทราบในปัจจุบันไปยัง v (dist[v]) หรือไม่ หากสั้นกว่า ระยะทางจะถูกอัปเดต (ผ่อนคลาย) และ v จะถูกเพิ่มเข้าไปในคิวลำดับความสำคัญด้วยระยะทางใหม่

ต้นไม้เส้นทางที่สั้นที่สุด (Shortest path tree) คืออะไร?

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

การประยุกต์ใช้อัลกอริทึมของไดค์สตราในโลกแห่งความเป็นจริงมีอะไรบ้าง?

อัลกอริทึมของไดค์สตราถูกใช้ในระบบนำทาง GPS, โปรโตคอลการกำหนดเส้นทางเครือข่าย (OSPF, IS-IS), การวิเคราะห์เครือข่ายสังคม, การเพิ่มประสิทธิภาพเส้นทางสายการบิน, การวางแผนเส้นทางหุ่นยนต์, การค้นหาเส้นทาง AI ในเกม, โลจิสติกส์โซ่อุปทาน และการออกแบบเครือข่ายโทรคมนาคม ปัญหาใดๆ ที่สามารถจำลองเป็นการค้นหาเส้นทางที่สั้นที่สุดหรือประหยัดที่สุดในกราฟจะได้รับประโยชน์จากอัลกอริทึมนี้

แหล่งข้อมูลเพิ่มเติม

อ้างอิงเนื้อหา หน้าหรือเครื่องมือนี้ว่า:

"เครื่องคำนวณเส้นทางสั้นสุดของไดค์สตรา" ที่ https://MiniWebtool.com/th// จาก MiniWebtool, https://MiniWebtool.com/

โดยทีมงาน miniwebtool อัปเดตเมื่อ: 19 ก.พ. 2026

คุณสามารถลองใช้ AI แก้ปัญหาคณิตศาสตร์ GPT ของเรา เพื่อแก้ไขปัญหาทางคณิตศาสตร์ของคุณผ่านคำถามและคำตอบด้วยภาษาธรรมชาติ.

เครื่องคำนวณเส้นทางสั้นสุดของไดค์สตรา

ตัวบล็อกโฆษณาของคุณทำให้เราไม่สามารถแสดงโฆษณาได้

เกี่ยวกับ เครื่องคำนวณเส้นทางสั้นสุดของไดค์สตรา

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

รหัสเทียม (Pseudocode) ของอัลกอริทึม

สูตรหลัก

วิธีใช้งานเครื่องคำนวณนี้

ทำความเข้าใจผลลัพธ์

ตารางระยะทาง

การแสดงภาพกราฟ

การติดตามทีละขั้นตอน

ความซับซ้อนของเวลา (Time Complexity)

กราฟแบบมีทิศทางเทียบกับไม่มีทิศทาง

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

การประยุกต์ใช้ในโลกแห่งความเป็นจริง

การนำทาง GPS

การกำหนดเส้นทางเครือข่าย

การวิเคราะห์เครือข่ายสังคม

การพัฒนาเกม

โซ่อุปทานและโลจิสติกส์

คำถามที่พบบ่อย

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

อัลกอริทึมของไดค์สตราสามารถจัดการกับน้ำหนักขอบที่เป็นลบได้หรือไม่?

กราฟแบบมีทิศทางและไม่มีทิศทางแตกต่างกันอย่างไร?

การผ่อนคลายขอบ (Edge relaxation) ในอัลกอริทึมของไดค์สตราคืออะไร?

ต้นไม้เส้นทางที่สั้นที่สุด (Shortest path tree) คืออะไร?

การประยุกต์ใช้อัลกอริทึมของไดค์สตราในโลกแห่งความเป็นจริงมีอะไรบ้าง?

แหล่งข้อมูลเพิ่มเติม

เครื่องมือเด่น:

Priority Queue	ความซับซ้อนของเวลา	เหมาะสำหรับ
Binary Heap	\( O((V + E) \log V) \)	ใช้งานทั่วไป, กราฟแบบเบาบาง (sparse graphs)
Fibonacci Heap	\( O(V \log V + E) \)	กราฟแบบหนาแน่น (dense graphs) (ในทางทฤษฎี)
Array (no heap)	\( O(V^2) \)	กราฟที่หนาแน่นมาก, จำนวน V น้อย