使用FGL查找最短路徑

Question

我使用Martin Erwig的函數圖庫（FGL）來表示以下簡單有向權重圖。

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 

現在我想找到一個節點到另一個節點如最短路徑使用dijkstra算法的A至E。似乎有這樣做的函數Data.Graph.Inductive.Query.SP：

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

但我無法弄清楚如何從提供的接口使用。任何幫助將非常感激。我還想聽聽其他建議，如果我是以正確的方式創建定向加權圖，或者是否有任何其他（更好的）包可以這樣做？

Answer 1

爲了讓兩個節點之間的最短路徑，該模塊提供了一個特殊的功能，sp（以下簡稱「最短路徑」，大概），因此要獲得的最短路徑最簡單的方法是

sp 1 5 mygraph 

sp使用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 

，並從你可以看到你如何能產生生成樹，並從自己獲得的最短路徑，但除非你有一個很好的理由不使用提供的功能，你應該堅持。