Package ghidra.graph.algo
Class DijkstraShortestPathsAlgorithm.OneSourceToAll
 java.lang.Object

 ghidra.graph.algo.DijkstraShortestPathsAlgorithm.OneSourceToAll

 Enclosing class:
 DijkstraShortestPathsAlgorithm<V,E extends GEdge<V>>
protected class DijkstraShortestPathsAlgorithm.OneSourceToAll extends java.lang.Object
A class representing all optimal paths from a given source to every other (reachable) vertex in the graph This is the workhorse of path computation, and implements Dijkstra's Shortest Path algorithm from one source to all destinations. We considered using JUNG to store the graph and compute the paths, but we could not, because we would like to find all paths having the optimal distance. If there are ties, JUNG's implementation chooses one arbitrarily; we would like all tied paths.


Field Summary
Fields Modifier and Type Field Description protected java.util.Map<V,java.util.Set<E>>
bestIns
protected DynamicValueSortedTreeMap<V,java.lang.Double>
queueByDistance
protected V
source
protected java.util.Map<V,java.lang.Double>
visitedDistance

Constructor Summary
Constructors Modifier Constructor Description protected
OneSourceToAll(V src)
Compute the shortest paths from a given vertex to all other reachable vertices in the graph

Method Summary
All Methods Instance Methods Concrete Methods Modifier and Type Method Description protected boolean
addOrUpdate(V dest, double newDist)
Update the record for the given destination with a new offer of shortest distance If either the record doesn't exist yet, or the new offer beats the current best, then a new record is created and replaces the current record.protected void
addPathsTo(java.util.Collection<java.util.Deque<E>> paths, V dst)
Add the shortest paths from the source to the given destination into the given collection This is used internally to recover the shortest pathsprotected void
addPathsTo(java.util.Collection<java.util.Deque<E>> paths, V prev, java.util.Deque<E> soFar)
Add the shortest paths from source to a given intermediate, continuing along a given path to the final destination, into the given collection This is a recursive method for constructing the shortest paths overall.java.util.Collection<java.util.Deque<E>>
computeOptimalPathsTo(V dst)
Recover the shortest paths from the source to the given destination, if it is reachableprotected void
fill()
Compute paths, building out the graph until all reachable vertices have been visitedprotected void
fillStep(V from, double dist)
Perform one iteration of Dijskstra's path finding algorithm



Field Detail

queueByDistance
protected final DynamicValueSortedTreeMap<V,java.lang.Double> queueByDistance

visitedDistance
protected final java.util.Map<V,java.lang.Double> visitedDistance

source
protected final V source


Constructor Detail

OneSourceToAll
protected OneSourceToAll(V src)
Compute the shortest paths from a given vertex to all other reachable vertices in the graph Parameters:
src
 the source (seed) vertex


Method Detail

computeOptimalPathsTo
public java.util.Collection<java.util.Deque<E>> computeOptimalPathsTo(V dst)
Recover the shortest paths from the source to the given destination, if it is reachable Parameters:
dst
 the destination Returns:
 a collection of the shortest paths from source to destination, or the empty set

addPathsTo
protected void addPathsTo(java.util.Collection<java.util.Deque<E>> paths, V dst)
Add the shortest paths from the source to the given destination into the given collection This is used internally to recover the shortest paths Parameters:
paths
 a place to store the recovered pathsdst
 the destination

addPathsTo
protected void addPathsTo(java.util.Collection<java.util.Deque<E>> paths, V prev, java.util.Deque<E> soFar)
Add the shortest paths from source to a given intermediate, continuing along a given path to the final destination, into the given collection This is a recursive method for constructing the shortest paths overall. Assuming the given path from intermediate to final destination is the shortest, we can show by induction, the computed paths from source to destination are the shortest. Parameters:
paths
 a place to store the recovered pathsprev
 the intermediate destinationsoFar
 a (shortest) path from intermediate to final destination

addOrUpdate
protected boolean addOrUpdate(V dest, double newDist)
Update the record for the given destination with a new offer of shortest distance If either the record doesn't exist yet, or the new offer beats the current best, then a new record is created and replaces the current record. If present, the list of best inbound edges is cleared  because they all correspond to a distance that has just been beat. The node is also added and/or moved forward in the queue of unvisited vertices. If the record exists, and the new offer ties the current offer, nothing happens, but the method still returns true, since the corresponding inbound edge could be optimal. If the record's current best beats the offer, nothing happens, and the method returns false, indicating the inbound edge is definitely not optimal. Parameters:
dest
 the destination whose record to updatenewDist
 the distance offer Returns:
 true iff the offer is equal to or better than the record's current best

fill
protected void fill()
Compute paths, building out the graph until all reachable vertices have been visited

fillStep
protected void fillStep(V from, double dist)
Perform one iteration of Dijskstra's path finding algorithm Parameters:
from
 the vertex to visit for this iteration

