Wyszukiwanie najkrótszej ścieżki z FGL

Question

Używam Funkcjonalnej biblioteki wykresów (FGL) firmy Martin Erwig do przedstawienia następującego prostego, wyważonego, ważonego wykresu.

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 

Teraz chcę znaleźć najkrótszą drogę od jednego węzła do drugiego np A do E przy użyciu algorytmu dijkstry. Wydaje się, że funkcja to zrobić w Data.Graph.Inductive.Query.SP:

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

Ale nie jestem w stanie dowiedzieć się, jak z niego korzystać z interfejsu usług. Każda pomoc byłaby bardzo cenna. Chciałbym również usłyszeć inne sugestie, jeśli tworzę odpowiednio ukierunkowany wykres ważony, czy jest jakikolwiek inny (lepszy) pakiet, aby to zrobić?

Answer 1

Aby uzyskać najkrótszą ścieżkę między dwoma węzłami, moduł zapewnia specjalną funkcję, sp (skrót od „najkrótszą drogą”, prawdopodobnie), więc najprostszym sposobem, aby uzyskać najkrótszej ścieżki jest

sp 1 5 mygraph 

sp wykorzystuje 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 

i od których można zobaczyć, jak można produkować drzewa rozpinającego i uzyskać najkrótszą drogę od tego samemu, ale jeśli masz bardzo dobry powód, aby nie korzystać z funkcji pod warunkiem, powinieneś trzymać się tego.