DijkstraShortestPathsAlgorithm

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 java.lang.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
Change	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 This is the workhorse of path computation, and implements Dijkstra's Shortest Path algorithm from one source to all destinations.

Field Summary

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

Constructor Summary

Constructors
Change	Constructor	Description
`DijkstraShortestPathsAlgorithm(GImplicitDirectedGraph<V,E> graph)`	Use Dijkstra's algorithm on the given graph This constructor assumes the graph's edges are `GWeightedEdge`s.
`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.
`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

All Methods Instance Methods Concrete Methods
Change	Modifier and Type	Method	Description
	`java.util.Collection<java.util.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.
	`java.util.Map<V,java.lang.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 Detail

sources NEW

protected final java.util.Map<V,DijkstraShortestPathsAlgorithm.OneSourceToAll> sources

graph NEW

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

maxDistance NEW
```
protected final double maxDistance
```

metric NEW

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

Constructor Detail

DijkstraShortestPathsAlgorithm
```
public DijkstraShortestPathsAlgorithm(GImplicitDirectedGraph<V,E> graph)
```
Use Dijkstra's algorithm on the given graph This constructor assumes the graph's edges are GWeightedEdges. 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,
                                      double maxDistance)
```
Use Dijkstra's algorithm on the given graph with the given maximum distance This constructor assumes the graph's edges are GWeightedEdges. 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

maxDistance - the maximum distance, or null for no maximum

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 Detail
- getDistancesFromSource
```
public java.util.Map<V,java.lang.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 java.util.Collection<java.util.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