Package graphs.shortestpaths

Class BellmanFordSolver<V>

java.lang.Object

graphs.shortestpaths.BellmanFordSolver<V>

Type Parameters:

V - the type of vertices.

All Implemented Interfaces:

ShortestPathSolver<V>

public class BellmanFordSolver<V>
extends Object
implements ShortestPathSolver<V>

Bellman-Ford algorithm implementation of the ShortestPathSolver interface.

See Also:

ShortestPathSolver

Nested Class Summary

Nested classes/interfaces inherited from interface graphs.shortestpaths.ShortestPathSolver

ShortestPathSolver.Constructor<V>

Field Summary

Fields

Modifier and Type	Field	Description
private Map<V,Double>	distTo
private Map<V,Edge<V>>	edgeTo

Constructor Summary

Constructors

Constructor	Description
BellmanFordSolver(Graph<V> graph, V start)	Constructs a new instance by executing Bellman-Ford algorithm on the graph from the start.

Method Summary

Modifier and Type	Method	Description
List<V>	solution(V goal)	Returns the single-pair shortest path from a start vertex to the goal.
private List<V>	vertices(Graph<V> graph, V start)

Methods inherited from class java.lang.Object

clone, equals, getClass, hashCode, notify, notifyAll, toString, wait, wait, wait

Field Detail

edgeTo

private final Map<V,Edge<V>> edgeTo

distTo

private final Map<V,Double> distTo

Constructor Detail

BellmanFordSolver

public BellmanFordSolver(Graph<V> graph,
                         V start)

Constructs a new instance by executing Bellman-Ford algorithm on the graph from the start.

Parameters:

graph - the input graph.

start - the start vertex.

Method Detail

solution

public List<V> solution(V goal)

Description copied from interface: ShortestPathSolver

Returns the single-pair shortest path from a start vertex to the goal.

Specified by:

solution in interface ShortestPathSolver<V>

Parameters:

goal - the goal vertex.

Returns:

a list of vertices representing the shortest path.

vertices

private List<V> vertices(Graph<V> graph,
                         V start)