# SuanShu, a Java numerical and statistical library

com.numericalmethod.suanshu.graph.algorithm.shortestpath

## Class Dijkstra<V>

• java.lang.Object
• com.numericalmethod.suanshu.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.
Wikipedia: Dijkstra's algorithm

• ### 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 interface ShortestPath<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 interface ShortestPath<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 if v is inaccessible from the source