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 GWeightedEdges. 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 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

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