ทำความรู้จักกับ Dijkstra Algorithm: การค้นหาเส้นทางที่สั้นที่สุดด้วย Haskell

 

 

Dijkstra Algorithm คืออะไร?

Dijkstra Algorithm เป็นอัลกอริธึมที่ใช้ในการค้นหาเส้นทางที่สั้นที่สุดจากต้นทาง (source) ไปยังจุดหมาย (target) ในกราฟที่มีน้ำหนัก (weighted graph) หรือกราฟที่มีการเชื่อมโยงระหว่างโหนดต่าง ๆ ซึ่งน้ำหนักจะระบุค่าต้นทุน (cost) การเดินทางจากโหนดหนึ่งไปยังอีกโหนดหนึ่งได้

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

 

การใช้งาน Dijkstra Algorithm

การประยุกต์ใช้ในชีวิตประจำวัน

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

 

ตัวอย่างโค้ด Dijkstra Algorithm ด้วย Haskell

ต่อไปนี้คือวิธี implement Dijkstra Algorithm ในภาษา Haskell โดยใช้ Data Structures เพื่อติดตามโหนดและน้ำหนัก:

 import qualified Data.Map as Map
import qualified Data.Set as Set
import Data.Maybe (fromMaybe)

type Graph = Map.Map String (Map.Map String Int)
type DistanceMap = Map.Map String Int
type PredecessorMap = Map.Map String (Maybe String)

dijkstra :: Graph -> String -> DistanceMap -> PredecessorMap -> DistanceMap
dijkstra graph source distances predecessors =
    let
        -- Helper function to find the node with the minimum distance
        minNode distMap visited =
            Map.foldrWithKey (\k v (mn, md) ->
                if not (Set.member k visited) && (v < md)
                then (Just k, v)
                else (mn, md)) (Nothing, maxBound) distMap

        -- The main loop to process the graph
        loop distances predecessors visited
            | Map.null distances = (distances, predecessors)
            | otherwise =
                let
                    (current, currentDist) = minNode distances visited
                    visited' = Set.insert (fromMaybe "" current) visited
                    neighbors = fromMaybe Map.empty (Map.lookup (fromMaybe "" current) graph)
                    updatedDistances = foldl (\distMap (nbr, wgt) ->
                        let newDist = currentDist + wgt
                        in if newDist < fromMaybe maxBound (Map.lookup nbr distMap)
                            then Map.insert nbr newDist distMap
                            else distMap) distances (Map.toList neighbors)
                    updatedPredecessors = foldl (\predMap (nbr, _) ->
                        Map.insert nbr (Just (fromMaybe "" current)) predMap) predecessors (Map.toList neighbors)
                in
                    loop (Map.delete (fromMaybe "" current) updatedDistances) updatedPredecessors visited'
    in
        fst (loop (Map.singleton source 0 `Map.union` distances) predecessors Set.empty)

-- Example Graph
exampleGraph :: Graph
exampleGraph = Map.fromList [
    ("A", Map.fromList [("B", 1), ("C", 4)]),
    ("B", Map.fromList [("C", 2), ("D", 5)]),
    ("C", Map.fromList [("D", 1)]),
    ("D", Map.empty)
    ]

-- Running Dijkstra
main :: IO ()
main = do
    let source = "A"
    let distances = dijkstra exampleGraph source (Map.empty) (Map.empty)
    putStrLn "Shortest distances from A:"
    print distances

ในโค้ดด้านบน เราได้สร้างกราฟตัวอย่างที่มีโหนดสี่โหนด จากนั้นเราใช้ฟังก์ชัน `dijkstra` เพื่อคำนวณระยะทางที่สั้นที่สุดจากโหนด A ไปยังโหนดอื่น ๆ ผลลัพธ์จะถูกเก็บไว้ใน `DistanceMap` ที่แสดงถึงต้นทุนการเดินทางจากโหนดต้นทางไปยังโหนดทุกโหนดในกราฟ

 

วิเคราะห์เวลาและความซับซ้อน

เวลาที่ Dijkstra Algorithm ใช้ในการหาทางที่สั้นที่สุดนั้นขึ้นอยู่กับการใช้โครงสร้างข้อมูล:

- เวลาในการหาตำแหน่งน้อยที่สุด: O(V^2) โดย V คือจำนวนโหนดในกราฟ หากเราใช้โครงสร้างข้อมูลที่ดีขึ้น เช่น priority queue (min heap) ก็จะทำให้สามารถลดเวลาในการหาน้อยที่สุดลงให้เหลือ O(E log V) โดย E คือจำนวนขอบ (edges)

- ความซับซ้อนทางเวลา: O(V^2) หรือ O(E log V) ขึ้นอยู่กับการนำไปใช้ร่วมกับโครงสร้างข้อมูลที่เหมาะสม

 

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

ข้อดี

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

ข้อเสีย

1. ไม่สามารถทำงานได้หากมีน้ำหนักเชิงลบ: ในกรณีที่กราฟมีน้ำหนักเชิงลบ อาจจะใช้ Bellman-Ford Algorithm แทน 2. ใช้เวลาและพื้นที่หน่วยความจำมาก: หากมีจำนวนโหนดและขอบ (edges) เยอะ อาจทำให้มีการใช้หน่วยความจำสูง 3. ไม่เหมาะกับกราฟที่ต้องใช้การปรับแต่งน้ำหนักบ่อย: ข้อมูลที่เปลี่ยนแปลงอาจจำเป็นต้องมีการคำนวณใหม่ทุกครั้ง

 

สรุปความรู้เกี่ยวกับ Dijkstra Algorithm

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

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

 

 

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