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

，并从你可以看到你如何能产生生成树，并从自己获得的最短路径，但除非你有一个很好的理由不使用提供的功能，你应该坚持。