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

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 GImplicitDirectedGraph<V,E>	graph
protected double	maxDistance
protected GEdgeWeightMetric<E>	metric
protected java.util.Map<V,DijkstraShortestPathsAlgorithm.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
java.util.Collection<java.util.Deque<E>>	computeOptimalPaths(V src, V dst)	Compute the shortest paths from the given source to the given destination
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

protected final java.util.Map<V,DijkstraShortestPathsAlgorithm.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 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

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