V
- the graph vertex typeE
- the graph edge typepublic class EppsteinShortestPathIterator<V,E> extends Object implements Iterator<GraphPath<V,E>>
This implementation can only be used for directed simple graphs. Also 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.
First the shortest paths tree in the edge reversed graph starting at sink
is built. Thus
we get distances $d(v)$ from every vertex $v$ to sink
. We then define a sidetrack edge to
be an edge, which is not in the shortest paths tree. The key observation is that every path
between the source
and the sink
can be solely determined by a sub-sequence of its
edges which are sidetracks.
Let $d(v)$ be the distance from $v$ to sink
and $w()$ be the weight function for edges in
graph
. If $e$ connects a pair of vertices $(u, w)$, the $\delta(e)$ is defined as
$w(e)+d(w)-d(u)$. Intuitively, $\delta(e)$ measures how much distance is lost by being
“sidetracked” along $e$ instead of taking a shortest path to sink
.
The idea of the algorithm is to build a heap of sidetracks. This heap can be then traversed with
breadth-first search in order to retrieve the implicit representations of the paths between
source
and sink
.
This implementation has several improvements in comparison to the original description in the article:
source
.Constructor and Description |
---|
EppsteinShortestPathIterator(Graph<V,E> graph,
V source,
V sink)
Constructs an instance of the algorithm for the given
graph , source and
sink . |
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
Copyright © 2020. All rights reserved.