Class AStarShortestDistanceFinder

A IShortestDistanceFinder implementation based on the A* algorithm, which is a refinement of the Dijkstra's algorithm, introducing a goal-oriented heuristic, driving the search in the direction of the end vertex.

Inheritance
System.Object
PotentialBasedShortestDistanceFinder
AStarShortestDistanceFinder
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 AStarShortestDistanceFinder : PotentialBasedShortestDistanceFinder, IPotentialBasedShortestDistanceFinder, IShortestDistanceFinder
Remarks

ALGORITHM
- The algorithm is described in DijkstraShortestDistanceFinder, with the only difference that edge distances are modified, based on a heuristic defined as a potential function.
- New edge distance is defined as follow: given the potential function P, for each edge (u, v) in the graph, d'(u, v) = d(u, v) + P(v) - P(u).
- If P is defined correctly, P(u) and P(v) are good approximations of the distance of u and v from the end vertex e.
- If so, P(v) - P(u) will be negative if moving from u to v gets us closer to e and positive if it gets us farther from it.
- For this reason, given two vertices v' and v'' connected from u via e' = (u, v') and e'' = (u, v''), and such that d(e') = d(e''), if P(v') < P(v'') then d'(e') < d''(e'), so the algorithm will prefer e' over e'' during the exploration, as it seems to be closer to e.
- Because the algorithm stops when e is processed, if the algorithm visits e earlier than later, the algorithm will find the shortest path from s to e ealier than later.

COMPLEXITY
- The complexity heavily depends on the accuracy of the potential function.
- A good model of the average performance of the algorithm is very complicated to derive, since the heuristic can drive the exploration much quicker or slower towards the end vertex, depending on how the function is defined.
- In general, potential functions which are closer to the actual shortest distance to the end vertex yield better results. The farther they move from the ideal, the less optimized the exploration of the graph becomes.
- Worst case remains as in DijkstraShortestDistanceFinder, where all vertices of the graph have to be explored, for a path from the start to the end to be found (or prove there is no path, since start and end lie in two different connected components).
- Best case is when P is the shortest distance to e, in which case only the vertices of a shortest path from s to e are visited (which is tipically a small fraction of the vertices of the graph, especially if the graph is large). That is the bare minimum to find the shortest path from s to e.
- Average case can even be worse than normal Dijkstra, if P is misleading, i.e. if it drives the exploration away from e, rather than reducing the cost of edges which drives the exploration closer to e.
- However, with a well defined P, close enough to the actual shortest distance, Time Complexity is between O(e + v * log(v)) and O(h), where h is the highest number of edges of a shortest path from s to e.
- Space Complexity is also between O(h) and O(v).

Constructors

| Improve this Doc View Source

AStarShortestDistanceFinder(Func<IUpdatablePriorityQueue<Int32>>)

Declaration
public AStarShortestDistanceFinder(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