9

I'm using Martin Erwig's Functional Graph Library (FGL) to represent the following simple directed weighted graph.

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

Now I want to find the shortest path from one node to another e.g. A to E using dijkstra's algorithm. There seems to be a function to do that in Data.Graph.Inductive.Query.SP:

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

But I'm not able to figure out how to use it from the interface provided. Any help would be much appreciated. I would also like to hear any other suggestions, if I'm creating the directed weighted graph the right way, or if there's any other (better) package to do so?

4

1 回答 1

6

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

从中您可以看到如何生成生成树并自己从中获得最短路径，但除非您有充分的理由不使用提供的函数，否则您应该坚持下去。

于 2012-10-28T23:51:47.240 回答