Tìm đường đi ngắn nhất với FGL

Question

Tôi đang sử dụng Thư viện đồ thị chức năng của Martin Erwig (FGL) để biểu thị biểu đồ có trọng số chỉ đạo đơn giản sau đây.

genLNodes :: [LNode String] 
genLNodes = zip [1..5] ["A","B","C","D","E"] 

genLEdges :: [LEdge Int] 
genLEdges = [(1,2,4),(1,3,1),(2,4,2),(3,4,2),(2,5,1),(4,5,1), 
      (2,1,4),(3,1,1),(4,2,2),(4,3,2),(5,2,1),(5,4,1)] 

mygraph :: Gr String Int 
mygraph = mkGraph genLNodes genLEdges 

Bây giờ tôi muốn tìm ra con đường ngắn nhất từ ​​nút này sang nút ví dụ khác A đến E bằng thuật toán dijkstra. Dường như có một chức năng để làm điều đó trong Data.Graph.Inductive.Query.SP:

dijkstra :: (Graph gr, Real b) => Heap b (LPath b) -> gr a b -> LRTree b 

Nhưng tôi không thể tìm ra cách để sử dụng nó từ giao diện được cung cấp. Bất kì sự trợ giúp nào đều được đánh giá cao. Tôi cũng muốn nghe bất kỳ đề xuất nào khác, nếu tôi tạo biểu đồ có trọng số trực tiếp đúng cách hoặc nếu có bất kỳ gói nào khác (tốt hơn) để làm như vậy?

Answer 1

Để có được con đường ngắn nhất giữa hai nút, các mô-đun cung cấp một chức năng đặc biệt, sp (viết tắt của "con đường ngắn nhất", có lẽ), vì vậy cách đơn giản nhất để có được con đường ngắn nhất là

sp 1 5 mygraph 

sp sử dụng dijkstra:

spTree :: (Graph gr, Real b) => Node -> gr a b -> LRTree b 
spTree v = dijkstra (H.unit 0 (LP [(v,0)])) 

sp :: (Graph gr, Real b) => Node -> Node -> gr a b -> Path 
sp s t = getLPathNodes t . spTree s 

và từ đó bạn có thể xem cách bạn có thể tạo ra các cây bao trùm và nhận được con đường ngắn nhất từ ​​đó cho mình, nhưng trừ khi bạn có một lý do rất tốt để không sử dụng chức năng cung cấp, bạn nên gắn bó với điều đó.