Finding shortest path with FGL

Question

I'm using Martin Erwig's Functional Graph Library (FGL) to represent the following simple directed 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 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?

Accepted Answer

To get the shortest path between two nodes, the module provides a special function, `sp` (short for "shortest path", presumably), so the simplest way to get the shortest path is

```
sp 1 5 mygraph
```

`sp` uses `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
```

and from that you can see how you could produce the spanning tree and get the shortest path from that yourself, but unless you have a very good reason to not use the provided function, you should stick with that.

Finding shortest path with FGL

Solution

Problem