V
- the graph vertex typeE
- the graph edge typepublic class YenShortestPathIterator<V,E> extends Object implements Iterator<GraphPath<V,E>>
For this iterator to work correctly the graph must not be modified during iteration. Currently there are no means to ensure that, nor to fail-fast. The results of such modifications are undefined.
The main idea of this algorithm is to divide each path between the source
and the
sink
into the root part - the part that coincides within some of the paths computed so far, and
the spur part, the part that deviates from all other paths computed so far. Therefore, for each path the
algorithm maintains a vertex, at which the path deviates from its "parent" path (the candidate path
using which it was computed).
First the algorithm finds the shortest path between the source
and the sink
,
which is put into the candidates heap. The source
is assigned to be its deviation vertex.
Then on each iteration the algorithm takes a candidate from the heap with minimum weight, puts it into the
result list and builds all possible deviations from it wrt. other paths, that are in the result list.
By generating spur paths starting only from the vertices that are after the deviation vertex of current
path (including the deviation vertex) it is possible to avoid building duplicated candidates.
Constructor and Description |
---|
YenShortestPathIterator(Graph<V,E> graph,
V source,
V sink)
Constructs an instance of the algorithm for given
graph ,
source and sink . |
YenShortestPathIterator(Graph<V,E> graph,
V source,
V sink,
Supplier<org.jheaps.AddressableHeap<Double,GraphPath<V,E>>> heapSupplier)
Constructs an instance of the algorithm for given
graph ,
source , sink and heapSupplier . |
Modifier and Type | Method and Description |
---|---|
boolean |
hasNext() |
GraphPath<V,E> |
next() |
clone, equals, finalize, getClass, hashCode, notify, notifyAll, toString, wait, wait, wait
forEachRemaining, remove
public YenShortestPathIterator(Graph<V,E> graph, V source, V sink)
graph
,
source
and sink
.graph
- graphsource
- source vertexsink
- sink vertexpublic YenShortestPathIterator(Graph<V,E> graph, V source, V sink, Supplier<org.jheaps.AddressableHeap<Double,GraphPath<V,E>>> heapSupplier)
graph
,
source
, sink
and heapSupplier
.graph
- graphsource
- source vertexsink
- sink vertexheapSupplier
- supplier of the preferable heap implementationCopyright © 2019. All rights reserved.