Package org.jgrapht.alg.shortestpath

Class BellmanFordPathElement<V,E>

java.lang.Object

org.jgrapht.alg.shortestpath.AbstractPathElement<V,E>

org.jgrapht.alg.shortestpath.BellmanFordPathElement<V,E>

final class BellmanFordPathElement<V,E>
extends AbstractPathElement<V,E>

Helper class for BellmanFordShortestPath; not intended for general use.

Field Summary

Fields

Modifier and Type	Field	Description
private double	cost
private double	epsilon

Fields inherited from class org.jgrapht.alg.shortestpath.AbstractPathElement

nHops, prevEdge, prevPathElement

Constructor Summary

Constructors

Modifier	Constructor	Description
(package private)	BellmanFordPathElement(BellmanFordPathElement<V,E> original)	Copy constructor.
protected	BellmanFordPathElement(Graph<V,E> graph, BellmanFordPathElement<V,E> pathElement, E edge, double cost, double epsilon)	Creates a path element by concatenation of an edge to a path element.
protected	BellmanFordPathElement(V vertex, double epsilon)	Creates an empty path element.

Method Summary

Modifier and Type	Method	Description
double	getCost()	Returns the total cost of the path element.
protected boolean	improve(BellmanFordPathElement<V,E> candidatePrevPathElement, E candidateEdge, double candidateCost)	Returns true if the path has been improved, false otherwise.

Methods inherited from class org.jgrapht.alg.shortestpath.AbstractPathElement

createEdgeListPath, getHopCount, getPrevEdge, getPrevPathElement, getVertex

Methods inherited from class java.lang.Object

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

Field Detail

cost

private double cost

epsilon

private double epsilon

Constructor Detail

BellmanFordPathElement

protected BellmanFordPathElement(Graph<V,E> graph,
                                 BellmanFordPathElement<V,E> pathElement,
                                 E edge,
                                 double cost,
                                 double epsilon)

Creates a path element by concatenation of an edge to a path element.

Parameters:

pathElement -

edge - edge reaching the end vertex of the path element created.

cost - total cost of the created path element.

epsilon - tolerance factor.

BellmanFordPathElement

BellmanFordPathElement(BellmanFordPathElement<V,E> original)

Copy constructor.

Parameters:

original - source to copy from

BellmanFordPathElement

protected BellmanFordPathElement(V vertex,
                                 double epsilon)

Creates an empty path element.

Parameters:

vertex - end vertex of the path element.

epsilon - tolerance factor.

Method Detail

getCost

public double getCost()

Returns the total cost of the path element.

Returns:

.

improve

protected boolean improve(BellmanFordPathElement<V,E> candidatePrevPathElement,
                          E candidateEdge,
                          double candidateCost)

Returns true if the path has been improved, false otherwise. We use an "epsilon" precision to check whether the cost has been improved (because of many roundings, a formula equal to 0 could unfortunately be evaluated to 10^-14).

Parameters:

candidatePrevPathElement -

candidateEdge -

candidateCost -

Returns:

.