dev.nm.graph.algorithm.shortestpath

Interface ShortestPath<V>

Type Parameters:

V - vertex type

All Known Implementing Classes:

Dijkstra

public interface ShortestPath<V>

In graph theory, a shortest path algorithm finds a path between two vertices in a graph such that the sum of the weights of its constituent edges is minimized.

See Also:

Wikipedia: Shortest path problem

Method Summary

Modifier and Type	Method and Description
double	distance(V v) Gets the shortest distance from the source to a vertex.
WeightedEdge<V>	lastEdge(V v) Gets the last edge of a vertex on its shortest distance from the source.

Method Detail

distance

double distance(V v)

Gets the shortest distance from the source to a vertex.

Parameters:

v - a vertex

Returns:

the shortest distance

lastEdge

WeightedEdge<V> lastEdge(V v)

Gets the last edge of a vertex on its shortest distance from the source.

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