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 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 final Map<V,Set<E>>
    bestIns
     
    protected final ValueSortedMap<V,Double>
    queueByDistance
     
    protected final V
    source
     
    protected final Map<V,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

    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
    protected void
    addPathsTo(Collection<Deque<E>> paths, V dst)
    Add the shortest paths from the source to the given destination into the given collection
    protected void
    addPathsTo(Collection<Deque<E>> paths, V prev, 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
    Collection<Deque<E>>
    computeOptimalPathsTo(V dst)
    Recover the shortest paths from the source to the given destination, if it is reachable
    protected void
    fill()
    Compute paths, building out the graph until all reachable vertices have been visited
    protected void
    fillStep(V from, double dist)
    Perform one iteration of Dijskstra's path finding algorithm

    Methods inherited from class java.lang.Object

    clone, equals, finalize, getClass, hashCode, notify, notifyAll, toString, wait, wait, wait

  • Field Details

    • queueByDistance

      protected final ValueSortedMap<V,Double> queueByDistance

    • visitedDistance

      protected final Map<V,Double> visitedDistance

    • bestIns

      protected final Map<V,Set<E extends GEdge<V>>> bestIns

    • source

      protected final V source

  • Constructor Details

    • 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 Details

    • computeOptimalPathsTo

      public Collection<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(Collection<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 paths
      dst - the destination

    • addPathsTo

      protected void addPathsTo(Collection<Deque<E>> paths, V prev, 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 paths
      prev - the intermediate destination
      soFar - 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 update
      newDist - 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