Class BidirectionalAStarShortestDistanceFinder

A IPotentialBasedShortestDistanceFinder implementation based on the bidirectional A* algorithm, which combines the goal-oriented heuristic of the A* algorithm and the double search approach of the bidirectional Dijkstra's algorithm.

Inheritance
System.Object
PotentialBasedShortestDistanceFinder
BidirectionalAStarShortestDistanceFinder
Implements
Inherited Members
System.Object.Equals(System.Object)
System.Object.Equals(System.Object, System.Object)
System.Object.GetHashCode()
System.Object.GetType()
System.Object.MemberwiseClone()
System.Object.ReferenceEquals(System.Object, System.Object)
System.Object.ToString()
Namespace: MoreStructures.Graphs.ShortestDistance
Assembly: MoreStructures.dll
Syntax
public class BidirectionalAStarShortestDistanceFinder : PotentialBasedShortestDistanceFinder, IPotentialBasedShortestDistanceFinder, IShortestDistanceFinder
Remarks

ALGORITHM
- Same as AStarShortestDistanceFinder, but with the use of the "bidirectional search approach" used in BidirectionalDijkstraShortestDistanceFinder to run Dijkstra's algorithm.

COMPLEXITY
- The bidirectional search cuts in half, in average, the exploration time of AStarShortestDistanceFinder.
- That improves average runtime, but doesn't change worst case scenarios and best case scenarios, since in those scenarios the number of vertices to visit is fixed and equal to v and h, respectively, and irrespective of whether the exploration is done unidirectionally or bidirectionally.
- Therefore, Time Complexity is O(e + v * log(v)) in the worst case, O(h) in the best case and somewhere in between, still lower than AStarShortestDistanceFinder, in all other cases.
- Space Complexity is between O(h) and O(v).

Constructors

| Improve this Doc View Source

BidirectionalAStarShortestDistanceFinder(Func<IUpdatablePriorityQueue<Int32>>)

Declaration
public BidirectionalAStarShortestDistanceFinder(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.

Implements

Extension Methods