Class DijkstraShortestDistanceTreeFinder
A IShortestDistanceTreeFinder implementation based on the Dijkstra algorithm.
Inheritance
Implements
Inherited Members
Namespace: MoreStructures.Graphs.ShortestDistanceTree
Assembly: MoreStructures.dll
Syntax
public class DijkstraShortestDistanceTreeFinder : IShortestDistanceTreeFinderRemarks
REQUIREMENTS
- Same as DijkstraShortestDistanceFinder.
ALGORITHM
- The algorithm closely resembles the one used in DijkstraShortestDistanceFinder, with the
following differences. Check that algorithm for further information.
- The main loop is only stopped when all vertices have been processed, instead of being stopped as soon as the
end vertex is found, and its shortest distance and path calculated.
- The path from the start vertex is not reconstructed, since that would need to be done for each of the
vertices of the graph, resulting in a worst case O(v^2) Space Complexity.
COMPLEXITY
- Same analysis as in DijkstraShortestDistanceFinder.
- The fact that the algorithm doesn't stop when a specific vertex is found, but goes through all vertices, has
an impact on the average performance, but doesn't affect the worst case scenario, since in the worst case the
end vertex is the last vertex processed of the graph.
- Therefore, as in single path Dijkstra's algorithm variant, Time Complexity is O(e + v * log(v)) with the
best available IUpdatablePriorityQueue<T> implementation
(UpdatableFibonacciHeapPriorityQueue<T>), O((e + v) * log(v)) when
using a UpdatableBinaryHeapPriorityQueue<T> and O((e + v) * v) when
using the naive implementation of ArrayListPriorityQueue<T>.
- Space Complexity is O(v), since all auxiliary structures contain a number of items proportional to v.
Constructors
| Improve this Doc View SourceDijkstraShortestDistanceTreeFinder(Func<IUpdatablePriorityQueue<Int32>>)
Declaration
public DijkstraShortestDistanceTreeFinder(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 SourceFindTree(IGraph, IGraphDistances, Int32)
Declaration
public BestPreviouses FindTree(IGraph graph, IGraphDistances distances, int start)Parameters
| Type | Name | Description |
|---|---|---|
| IGraph | graph | |
| IGraphDistances | distances | |
| System.Int32 | start |
Returns
| Type | Description |
|---|---|
| BestPreviouses |