รู้จักกับ Dijkstra Algorithm: หนทางสู่การหาค่าเส้นทางที่สั้นที่สุด ใน Fortran

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

Dijkstra Algorithm คืออะไร?

ง่ายๆ ก็คือ Dijkstra Algorithm เป็นขั้นตอนในการค้นหาค่าเส้นทางที่สั้นที่สุดจากจุดเริ่มต้น (Source Node) ไปยังจุดปลายทาง (Destination Node) ในกราฟที่มีน้ำหนัก อัลกอริธึมนี้เริ่มจากการกำหนดระยะทางเริ่มต้นจากโหนดเริ่มต้นเป็น 0 และระยะทางอื่น ๆ อีกทั้งหมดเป็น “อนันต์” (Infinity) แล้วทำการสำรวจค่าระยะทางที่สั้นที่สุดไปยังโหนดที่เชื่อมต่อกันอยู่ โดยอัปเดตค่าระยะทางที่สั้นที่สุดอย่างต่อเนื่อง

อธิบายการทำงาน

Usecase ในโลกจริง

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

ตัวอย่าง Code ใน Fortran

ต่อไปนี้จะเป็นตัวอย่างโค้ดการใช้งาน Dijkstra Algorithm ในภาษา Fortran:

 program Dijkstra
  implicit none
  integer, parameter :: INF = 9999
  integer :: graph(5, 5) = reshape([0, 10, 0, 30, 100, &
                                     10, 0, 50, 0, 0, &
                                     0, 50, 0, 20, 10, &
                                     30, 0, 20, 0, 60, &
                                     100, 0, 10, 60, 0], [5, 5])
  integer :: dist(5), visited(5), i, j, count, u
  integer :: num_nodes = 5

  ! Initializing the distance array
  dist = [INF, INF, INF, INF, INF]
  dist(1) = 0
  visited = 0

  ! Main Loop for Dijkstra
  do count = 1, num_nodes
    ! Find the unvisited node with the smallest distance
    u = minloc(dist * (1 - visited))
    visited(u) = 1

    ! Update the distance for neighbors
    do j = 1, num_nodes
      if (graph(u, j) > 0 .and. visited(j) == 0) then
        if (dist(u) + graph(u, j) < dist(j)) then
          dist(j) = dist(u) + graph(u, j)
        end if
      end if
    end do
  end do

  ! Output results
  print *, "Vertex Distance from Source Node"
  do i = 1, num_nodes
    print *, i, ' ', dist(i)
  end do

end program Dijkstra

วิเคราะห์ Complexity

Dijkstra Algorithm มีความซับซ้อนทางเวลา (Time Complexity) ที่ต่างกันขึ้นอยู่กับโครงสร้างข้อมูลที่ใช้ในการเก็บข้อมูลกราฟ โดยถ้าใช้การค้นหาโดยตรง (Linear Search) ค่าเวลาในการทำงานจะเป็น O(V^2) ซึ่ง V คือจำนวนโหนด ในขณะที่ถ้าใช้ Heap จะได้ค่าเวลาที่ลดลงเป็น O(E log V) ซึ่ง E คือจำนวนของเส้นเชื่อม

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

ข้อดี:

- ใช้งานง่ายและเข้าใจได้ง่าย

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

ข้อเสีย:

- ไม่สามารถใช้งานได้กับกราฟที่มีน้ำหนักลบ

- อาจมีปัญหาเมื่อกราฟมีความหนาแน่นสูง

สรุป

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

หากคุณต้องการศึกษาเพิ่มเติมเกี่ยวกับ Programming หรือ Algorithm ต่างๆ ที่น่าสนใจ แนะนำให้เข้ามาที่ EPT เพื่อเรียนรู้กับผู้สอนที่มีประสบการณ์!

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