Class BidirectionalDijkstraShortestDistanceFinder
A IShortestDistanceFinder implementation based on a refinement of the Dijkstra algorithm, running search in two parallel inversed flows: from the start vertext to the end vertex and viceversa.
Inheritance
Implements
Inherited Members
Namespace: MoreStructures.Graphs.ShortestDistance
Assembly: MoreStructures.dll
Syntax
public class BidirectionalDijkstraShortestDistanceFinder : IShortestDistanceFinderRemarks
REQUIREMENTS
- Same as DijkstraShortestDistanceFinder.
ALGORITHM
- The algorithm runs in parallel two searches: one from the start vertex s and the other one from the end
vertex e.
- The search from s is called forward search and is run on the provided directed graph, with the
provided distance function, as it is done in a normal Dijkstra's algorithm execution.
- The search from e is called backward search and is run on the reversed graph, with a reversed distance
function: reversedDistance(edgeStart, edgeEnd) = distance(edgeEnd, edgeStart).
- Each search has its own dictionary BP, set A, priority queue PQ and last added vertex LA, which are described
in detail in DijkstraShortestDistanceFinder. Data structures for the forward search are called
here BPf, Af, PQf and LAf. Data structures for the backward search are called here BPb, Ab, PQb, LAb.
- After standard initialization of the two searches (which is different since they have different starting
vertex, hence different A and BP initial content etc), the two searches are executed.
- The "parallelism" is done by running a single step of one of the two searches at each iteration, and
alternating between the two searches: first a step forward, then a step backward, then a step forward, etc.
- The iterations continue until either a meeting point vertex v has been processed and added to both Af and Ab,
or both searches are done (i.e. no more edges to explore).
- If the meeting point vertex v hasn't been found before the two searches would run out of edges to explore,
it means that e is not reachable from s, and System.Int32.MaxValue and an empty path are returned as
result.
- Otherwise, a path from s to e exists. However, such a path doesn't necessarily goes through v.
- Therefore, the vertex u, of a shortest path from s to e and such that u is known to both BPf and BPb, with
the correct shortest path estimates in both directions, has to be found.
- It can be proven that such a vertex u exists, which also belongs to Af or Ab or to both.
- Therefore, all vertices in both BPf and BPf are scanned, and the one minimizing the sum of estimates, from s
and e respectively, is taken.
- The full shortest path from s to e is then reconstructed by joining the two subpaths, going from s to u and
from u to e respectively.
- The shortest path distance is simply the sum of shortest distances for u in BPf and BPb.
COMPLEXITY
- The worst case analysis is the same as for DijkstraShortestDistanceFinder: in the worst
scenario, all vertices have to be explored, before finding the meeting point or concluding that there is no
path from s to e.
- Rebuilding the final path doesn't change the overall complexity, since calculating the intersection between
Af and Ab and finding the vertex minimizing the sum of estimates in BP are both linear time operations.
- Therefore, Time Complexity is O((v + e) * v), O((v + e) * log(v)) or O(e + v * log(v)), depending on the
IUpdatablePriorityQueue<T> implementation chosen, as described in the documentation of
DijkstraShortestDistanceFinder. Space Complexity remains O(v).
- While it is true that running the search both from the start and from the end doesn't help asymptotic
complexity in the worst case, it does help in the average case, i.e. on the expected number of iterations
before the algorithm stops adding vertices.
- Intuitively, while a single run of Dijkstra's algorithm from s to e, at distance d = 2 * r from each other,
has to explore an area of the graph proportional to Pi * d^2 = 4 * Pi * r^2, a bidirectional Dijkstra's
execution explores in average an area proportional to 2 * Pi * r^2. So, half of the area.
Constructors
| Improve this Doc View SourceBidirectionalDijkstraShortestDistanceFinder(Func<IUpdatablePriorityQueue<Int32>>)
Declaration
public BidirectionalDijkstraShortestDistanceFinder(Func<IUpdatablePriorityQueue<int>> priorityQueueBuilder)Parameters
| Type | Name | Description |
|---|---|---|
| Func<IUpdatablePriorityQueue<System.Int32>> | priorityQueueBuilder | A builder of a IUpdatablePriorityQueue<T> of System.Int32 values, used by the algorithm to store edges with priority from the closest to the start, to the farthest. |
Methods
| Improve this Doc View SourceFind(IGraph, IGraphDistances, Int32, Int32)
Declaration
public (int, IList<int>) Find(IGraph graph, IGraphDistances distances, int start, int end)Parameters
| Type | Name | Description |
|---|---|---|
| IGraph | graph | |
| IGraphDistances | distances | |
| System.Int32 | start | |
| System.Int32 | end |
Returns
| Type | Description |
|---|---|
| System.ValueTuple<System.Int32, IList<System.Int32>> |