使用FGL查找最短路径

Question

使用FGL查找最短路径

9

我正在使用Martin Erwig的函数图形库（FGL）来表示以下简单有向加权图。 graph

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

但我无法从提供的界面中弄清如何使用它。如果有任何帮助，将不胜感激。此外，如果我正确地创建了有向加权图，或者是否有其他（更好的）包来实现它，我也想听听其他建议。

- vis

1个回答

网页内容由stack overflow 提供, 点击上面的

可以查看英文原文，
原文链接

- Daniel Fischer · Accepted Answer

为了获得两个节点之间的最短路径，该模块提供了一个特殊函数 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

从这里可以看出如何生成生成树并自己得到最短路径，但是除非你有非常充分的理由不使用提供的函数，否则你应该坚持使用它。