Class Dijkstra<V>
- java.lang.Object
-
- dev.nm.graph.algorithm.shortestpath.Dijkstra<V>
-
- Type Parameters:
V
- vertex type
- All Implemented Interfaces:
ShortestPath<V>
public class Dijkstra<V> extends Object implements ShortestPath<V>
Dijkstra's algorithm is a graph search algorithm that solves the single-source shortest path problem for a graph with non-negative edge path costs, producing a shortest path tree. This implementation based on a min-priority queue implemented by a Fibonacci heap runs in \(O(|E|+|V|\log|V|)\). It is asymptotically the fastest known single-source shortest-path algorithm for arbitrary directed graphs with unbounded non-negative weights.- See Also:
- Wikipedia: Dijkstra's algorithm
-
-
Method Summary
All Methods Instance Methods Concrete Methods Modifier and Type Method Description double
distance(V v)
Gets the shortest distance from the source to a vertex.WeightedArc<V>
lastEdge(V v)
Gets the last edge of a vertex on its shortest distance from the source.
-
-
-
Constructor Detail
-
Dijkstra
public Dijkstra(DiGraph<V,? extends WeightedArc<V>> g, V source)
-
-
Method Detail
-
distance
public double distance(V v)
Description copied from interface:ShortestPath
Gets the shortest distance from the source to a vertex.- Specified by:
distance
in interfaceShortestPath<V>
- Parameters:
v
- a vertex- Returns:
- the shortest distance
-
lastEdge
public WeightedArc<V> lastEdge(V v)
Description copied from interface:ShortestPath
Gets the last edge of a vertex on its shortest distance from the source.- Specified by:
lastEdge
in interfaceShortestPath<V>
- Parameters:
v
- a vertex that is different from the source- Returns:
- the last edge of a vertex on its shortest distance from the source;
null
ifv
is inaccessible from the source
-
-