Package ghidra.graph.algo

# Class DijkstraShortestPathsAlgorithm<V,E extends GEdge<V>>

java.lang.Object
ghidra.graph.algo.DijkstraShortestPathsAlgorithm<V,E>

Type Parameters:
  `V` - the type of vertices
  `E` - the type of edges

public class DijkstraShortestPathsAlgorithm<V,E extends GEdge<V>> extends Object
Dijkstra's shortest-path algorithm

This implementation computes the shortest paths between two vertices using Dijkstra's single-source shortest path finding algorithm. Any time a new source is given, it explores all destinations in the graph up to a maximum distance from the source. Thus, this implementation is best applied when many queries are anticipated from relatively few sources.

- ## Nested Class Summary

  Nested Classes
  Modifier and Type
  Class
  Description
  `protected class`
  `DijkstraShortestPathsAlgorithm.OneSourceToAll`
  A class representing all optimal paths from a given source to every other (reachable) vertex in the graph

- ## Field Summary

  Fields
  Modifier and Type
  Field
  Description
  `protected final GImplicitDirectedGraph<V,E>`
  `graph`
  `protected final double`
  `maxDistance`
  `protected final GEdgeWeightMetric<E>`
  `metric`
  `protected final Map<V,DijkstraShortestPathsAlgorithm<V,E>.OneSourceToAll>`
  `sources`

- ## Constructor Summary

  Constructors
  Constructor
  Description
  `DijkstraShortestPathsAlgorithm(GImplicitDirectedGraph<V,E> graph)`
  Use Dijkstra's algorithm on the given graph
  `DijkstraShortestPathsAlgorithm(GImplicitDirectedGraph<V,E> graph, double maxDistance)`
  Use Dijkstra's algorithm on the given graph with the given maximum distance
  `DijkstraShortestPathsAlgorithm(GImplicitDirectedGraph<V,E> graph, double maxDistance, GEdgeWeightMetric<E> metric)`
  Use Dijstra's algorithm on the given graph with the given maximum distance and a custom edge weight metric
  `DijkstraShortestPathsAlgorithm(GImplicitDirectedGraph<V,E> graph, GEdgeWeightMetric<E> metric)`
  Use Dijstra's algorithm on the given graph with a custom edge weight metric

- ## Method Summary

  Modifier and Type
  Method
  Description
  `Collection<Deque<E>>`
  `computeOptimalPaths(V src, V dst)`
  Compute the shortest paths from the given source to the given destination
  `Map<V,Double>`
  `getDistancesFromSource(V v)`
  Compute the shortest distance to all reachable vertices from the given source

  ### Methods inherited from class java.lang.Object

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

- ## Field Details

  - ### sources

    protected final Map<V,DijkstraShortestPathsAlgorithm<V,E extends GEdge<V>>.OneSourceToAll> sources

  - ### graph

    protected final GImplicitDirectedGraph<V,E extends GEdge<V>> graph

  - ### maxDistance

    protected final double maxDistance

  - ### metric

    protected final GEdgeWeightMetric<E extends GEdge<V>> metric

- ## Constructor Details

  - ### DijkstraShortestPathsAlgorithm

    public DijkstraShortestPathsAlgorithm(GImplicitDirectedGraph<V,E> graph)
    Use Dijkstra's algorithm on the given graph

    This constructor assumes the graph's edges are `GWeightedEdge`s. If not, you will likely encounter a `ClassCastException`.

    Parameters:
      `graph` - the graph

  - ### DijkstraShortestPathsAlgorithm

    public DijkstraShortestPathsAlgorithm(GImplicitDirectedGraph<V,E> graph, double maxDistance)
    Use Dijkstra's algorithm on the given graph with the given maximum distance

    This constructor assumes the graph's edges are `GWeightedEdge`s. If not, you will likely encounter a `ClassCastException`.

    Parameters:
      `graph` - the graph
      `maxDistance` - the maximum distance, or null for no maximum

  - ### DijkstraShortestPathsAlgorithm

    public DijkstraShortestPathsAlgorithm(GImplicitDirectedGraph<V,E> graph, GEdgeWeightMetric<E> metric)
    Use Dijstra's algorithm on the given graph with a custom edge weight metric
    Parameters:
      `graph` - the graph
      `metric` - the function to compute the weight of an edge

  - ### DijkstraShortestPathsAlgorithm

    public DijkstraShortestPathsAlgorithm(GImplicitDirectedGraph<V,E> graph, double maxDistance, GEdgeWeightMetric<E> metric)
    Use Dijstra's algorithm on the given graph with the given maximum distance and a custom edge weight metric
    Parameters:
      `graph` - the graph
      `maxDistance` - the maximum distance, or null for no maximum
      `metric` - the function to compute the weight of an edge

- ## Method Details

  - ### getDistancesFromSource

    public Map<V,Double> getDistancesFromSource(V v)
    Compute the shortest distance to all reachable vertices from the given source
    Parameters:
      `v` - the source vertex
    Returns:
      a map of destinations to distances from the given source

  - ### computeOptimalPaths

    public Collection<Deque<E>> computeOptimalPaths(V src, V dst)
    Compute the shortest paths from the given source to the given destination

    This implementation differs from typical implementations in that paths tied for the shortest distance are all returned. Others tend to choose one arbitrarily.

    Parameters:
      `src` - the source
      `dst` - the destination
    Returns:
      a collection of paths of shortest distance from source to destination