Julia: Erhalten vollständigen Pfad von Dijkstra-Funktion in Graphs.jl

Question

Gibt es eine Möglichkeit, vollständigen Pfad vom Quellknoten zum Zielknoten unter Verwendung Dijkstra algorithm von Graphs.jl-Modul zu erwerben?

Es gibt eine update_vertex! (Visitor, u, v, d) Methode, die aufgerufen wird, wenn die Entfernung zum Scheitelpunkt aktualisiert wird. Wird der Abstand nur aktualisiert, wenn ein neuer Scheitelpunkt gefunden wird, der zum kürzesten Pfad gehört? Ich bin mir nicht ganz sicher.

Danke.

Edit:

Laut Dokumentation besteht die Möglichkeit, kürzesten Weg zu rekonstruieren, mit Floyd-Warshall algorithm mit atributes dists und nexts aber ich bin nicht sicher, wie. Ich möchte es auf meinem GenericGraph laufen lassen.

Irgendeine Idee?

Answer 1

Das Ergebnis des Algorithmus enthält ein Feld namens parents als @DanGetz wies darauf hin. Jeder der Knoten hat den letzten Knoten, der besucht wurde, bevor er zu ihm kam (d. H. Der Übergeordnete auf dem kürzesten Weg). Mit den Eltern für jeden der Knoten, können Sie den kürzesten Weg für jeden von ihnen mit einer einfachen rekursiven Funktion Rückzieher:

spath(x, r, s) = x == s ? x : [spath(r.parents[x], r, s) x] 

wo r das Ergebnis des Dijkstra-Algorithmus ist und s die Quelle an sie übergeben ist.

Der kürzeste Pfad für jeden der Knoten kann durch List-Verständnis erhalten werden. Finden Sie unten das Ergebnis für die example in the documentation:

julia> [spath(x, r, 1) for x in g.vertices] 
5-element Array{Any,1}: 
1        
    1x3 Array{Int64,2}: 
1 3 2 
    1x2 Array{Int64,2}: 
1 3  
    1x4 Array{Int64,2}: 
1 3 2 4 
    1x3 Array{Int64,2}: 
1 3 5 

Es gibt wahrscheinlich bessere Algorithmen, es zu tun (das heißt einige dynamische Programmierverfahren erinnern Pfade für große Graphen), aber als Beispiel die rekursive Methode macht den Job.

---

A schnell Code Rekursion Ihre Wörterbücher mit mehreren Eltern für jeden kürzesten Weg angepasst:

function spath(current, parents, source, current_path) 
    if current == source || isempty(parents[current]) 
     return Any[[current; current_path]] 
    end 

    results = [] 
    for node in parents[current] 
     results = [spath(node, parents, source, [current; current_path]); results] 
    end 

    results 
end 

Hinweis der Strompfad als Parameter (Kopien davon) übergeben wird, bis der Blattknoten (source) und gibt somit den kürzesten Pfad zurück, wenn er erreicht wird. Auch hier ist es wahrscheinlich nicht die effizienteste Implementierung (ich bin kein Julia-Guru), aber es macht den Job.

Für Ihr Beispiel:

julia> parents = {2=>[1,3],3=>[1],1=>[]} 
julia> [(i, spath(i, parents, 1, [])) for i in keys(parents)] 
3-element Array{Tuple{Any,Array{Any,1}},1}: 
(2,Any[Any[1,3,2],Any[1,2]]) 
(3,Any[Any[1,3]])   
(1,Any[Any[1]])