Den kürzesten Pfad mit FGL finden

Question

Den kürzesten Pfad mit FGL finden

8

Ich verwende Martin Erwigs Functional Graph Library (FGL), um den folgenden einfachen gewichteten gerichteten Graph darzustellen.

%Vor%

Ich möchte jetzt den kürzesten Weg von einem Knoten zum nächsten finden, z. A bis E mit dem Algorithmus von Dijkstra. Es scheint eine Funktion in Data.Graph.Inductive.Query.SP zu geben:

%Vor%

Aber ich bin nicht in der Lage, herauszufinden, wie man es von der bereitgestellten Schnittstelle verwendet. Jede Hilfe würde sehr geschätzt werden. Ich würde auch gerne andere Vorschläge hören, wenn ich den gerichteten gewichteten Graphen in der richtigen Weise erstelle, oder wenn es ein anderes (besseres) Paket dafür gibt?

algorithm haskell graph shortest-path

vis 28.10.2012, 23:30

quelle

1 Antwort

Tags und Links algorithm haskell graph shortest-path

Django: Verwenden von Annotate, Count und Distinct in einem Queryset Speicherbedarf für 'kurze' Felder in Dalvik?

score 6 · Accepted Answer

Um den kürzesten Pfad zwischen zwei Knoten zu erhalten, bietet das Modul eine spezielle Funktion: sp (Abkürzung für" Kürzester Pfad ", vermutlich), also ist der einfachste Weg, den kürzesten Pfad zu bekommen,

%Vor%

sp verwendet dijkstra :

%Vor%

und davon können Sie sehen, wie Sie den Spannbaum erzeugen und den kürzesten Weg von diesem selbst finden können, aber wenn Sie nicht einen sehr guten Grund haben, die angegebene Funktion nicht zu benutzen, sollten Sie dabei bleiben.