9

MartinErwigのFunctionalGraphLibrary（FGL）を使用して、次の単純な有向加重グラフを表現しています。

グラフ

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

ここで、たとえばダイクストラのアルゴリズムAを使用するために、あるノードから別のノードへの最短経路を見つけたいと思います。Eでそれを行う関数があるようですData.Graph.Inductive.Query.SP：

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

しかし、提供されたインターフェースからそれを使用する方法を理解することはできません。どんな助けでも大歓迎です。有向加重グラフを正しい方法で作成している場合、またはそれを行うための他の（より良い）パッケージがある場合は、他の提案も聞きたいですか？

4

1 に答える 1

6

2つのノード間の最短パスを取得するために、モジュールは特別な機能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 に答える