Finding the Shortest Way with FGL

Question

I use the Martin Ervig Functional Graphics Library (FGL) to represent the next simple oriented weighted 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, for example. A to E using dijkstra algorithm. There seems to be a function to do this in Data.Graph.Inductive.Query.SP :

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

But I can’t understand how to use it from the provided interface. Any help is appreciated. I would also like to hear any other suggestions if I correctly create a focused weighted schedule or if there is any other (best) package for this?

Answer 1

To get the shortest path between two nodes, the module provides a special function sp (at least for the shortest path), so the easiest way to get the shortest path

 sp 1 5 mygraph 

sp uses dijkstra :

 spTree :: (Graph gr, Real b) => Node -> gr ab -> LRTree b spTree v = dijkstra (H.unit 0 (LP [(v,0)])) sp :: (Graph gr, Real b) => Node -> Node -> gr ab -> Path sp st = getLPathNodes t . spTree s 

and from this you can see how you can create a spanning tree and get the shortest path from it, but if you have no good reason not to use the provided function, you should stick to this.