| | | 1 | | using MoreStructures.PriorityQueues; |
| | | 2 | | |
| | | 3 | | namespace MoreStructures.Graphs.ShortestDistance; |
| | | 4 | | |
| | | 5 | | /// <summary> |
| | | 6 | | /// A <see cref="IPotentialBasedShortestDistanceFinder"/> implementation based on the bidirectional A* algorithm, |
| | | 7 | | /// which combines the goal-oriented heuristic of the A* algorithm and the double search approach of the bidirectional |
| | | 8 | | /// Dijkstra's algorithm. |
| | | 9 | | /// </summary> |
| | | 10 | | /// <remarks> |
| | | 11 | | /// <para id="requirements"> |
| | | 12 | | /// <inheritdoc cref="AStarShortestDistanceFinder" path="/remarks/para[@id='requirements']"/> |
| | | 13 | | /// </para> |
| | | 14 | | /// <para id="algorithm"> |
| | | 15 | | /// ALGORITHM |
| | | 16 | | /// <br/> |
| | | 17 | | /// - Same as <see cref="AStarShortestDistanceFinder"/>, but with the use of the "bidirectional search approach" |
| | | 18 | | /// used in <see cref="BidirectionalDijkstraShortestDistanceFinder"/> to run Dijkstra's algorithm. |
| | | 19 | | /// </para> |
| | | 20 | | /// <para id="complexity"> |
| | | 21 | | /// COMPLEXITY |
| | | 22 | | /// <br/> |
| | | 23 | | /// - The bidirectional search cuts in half, in average, the exploration time of |
| | | 24 | | /// <see cref="AStarShortestDistanceFinder"/>. |
| | | 25 | | /// <br/> |
| | | 26 | | /// - That improves average runtime, but doesn't change worst case scenarios and best case scenarios, since in |
| | | 27 | | /// those scenarios the number of vertices to visit is fixed and equal to v and h, respectively, and irrespective |
| | | 28 | | /// of whether the exploration is done unidirectionally or bidirectionally. |
| | | 29 | | /// <br/> |
| | | 30 | | /// - Therefore, Time Complexity is O(e + v * log(v)) in the worst case, O(h) in the best case and somewhere in |
| | | 31 | | /// between, still lower than <see cref="AStarShortestDistanceFinder"/>, in all other cases. |
| | | 32 | | /// <br/> |
| | | 33 | | /// - Space Complexity is between O(h) and O(v). |
| | | 34 | | /// </para> |
| | | 35 | | /// </remarks> |
| | | 36 | | public class BidirectionalAStarShortestDistanceFinder : PotentialBasedShortestDistanceFinder |
| | | 37 | | { |
| | | 38 | | /// <inheritdoc cref="BidirectionalAStarShortestDistanceFinder"/> |
| | | 39 | | /// <param name="priorityQueueBuilder"> |
| | | 40 | | /// A builder of a <see cref="IUpdatablePriorityQueue{T}"/> of <see cref="int"/> values, used by the algorithm to |
| | | 41 | | /// store edges with priority from the closest to the start, to the farthest. |
| | | 42 | | /// </param> |
| | | 43 | | public BidirectionalAStarShortestDistanceFinder(Func<IUpdatablePriorityQueue<int>> priorityQueueBuilder) |
| | 30 | 44 | | : base(new BidirectionalDijkstraShortestDistanceFinder(priorityQueueBuilder)) |
| | 30 | 45 | | { |
| | 30 | 46 | | } |
| | | 47 | | } |