| | | 1 | | using MoreStructures.Graphs.ShortestDistance; |
| | | 2 | | using MoreStructures.PriorityQueues; |
| | | 3 | | |
| | | 4 | | namespace MoreStructures.Graphs.ShortestDistanceTree; |
| | | 5 | | |
| | | 6 | | /// <summary> |
| | | 7 | | /// A <see cref="IShortestDistanceTreeFinder"/> implementation based on the Dijkstra algorithm. |
| | | 8 | | /// </summary> |
| | | 9 | | /// <remarks> |
| | | 10 | | /// <para id="requirements"> |
| | | 11 | | /// REQUIREMENTS |
| | | 12 | | /// <br/> |
| | | 13 | | /// - Same as <see cref="DijkstraShortestDistanceFinder"/>. |
| | | 14 | | /// </para> |
| | | 15 | | /// <para id="algorithm"> |
| | | 16 | | /// ALGORITHM |
| | | 17 | | /// <br/> |
| | | 18 | | /// - The algorithm closely resembles the one used in <see cref="DijkstraShortestDistanceFinder"/>, with the |
| | | 19 | | /// following differences. Check that algorithm for further information. |
| | | 20 | | /// <br/> |
| | | 21 | | /// - The main loop is only stopped when all vertices have been processed, instead of being stopped as soon as the |
| | | 22 | | /// end vertex is found, and its shortest distance and path calculated. |
| | | 23 | | /// <br/> |
| | | 24 | | /// - The path from the start vertex is not reconstructed, since that would need to be done for each of the |
| | | 25 | | /// vertices of the graph, resulting in a worst case O(v^2) Space Complexity. |
| | | 26 | | /// </para> |
| | | 27 | | /// <para id="complexity"> |
| | | 28 | | /// COMPLEXITY |
| | | 29 | | /// <br/> |
| | | 30 | | /// - Same analysis as in <see cref="DijkstraShortestDistanceFinder"/>. |
| | | 31 | | /// <br/> |
| | | 32 | | /// - The fact that the algorithm doesn't stop when a specific vertex is found, but goes through all vertices, has |
| | | 33 | | /// an impact on the average performance, but doesn't affect the worst case scenario, since in the worst case the |
| | | 34 | | /// end vertex is the last vertex processed of the graph. |
| | | 35 | | /// <br/> |
| | | 36 | | /// - Therefore, as in single path Dijkstra's algorithm variant, Time Complexity is O(e + v * log(v)) with the |
| | | 37 | | /// best available <see cref="IUpdatablePriorityQueue{T}"/> implementation |
| | | 38 | | /// (<see cref="PriorityQueues.FibonacciHeap.UpdatableFibonacciHeapPriorityQueue{T}"/>), O((e + v) * log(v)) when |
| | | 39 | | /// using a <see cref="PriorityQueues.BinaryHeap.UpdatableBinaryHeapPriorityQueue{T}"/> and O((e + v) * v) when |
| | | 40 | | /// using the naive implementation of <see cref="PriorityQueues.ArrayList.ArrayListPriorityQueue{T}"/>. |
| | | 41 | | /// <br/> |
| | | 42 | | /// - Space Complexity is O(v), since all auxiliary structures contain a number of items proportional to v. |
| | | 43 | | /// </para> |
| | | 44 | | /// </remarks> |
| | | 45 | | public class DijkstraShortestDistanceTreeFinder : IShortestDistanceTreeFinder |
| | | 46 | | { |
| | 14 | 47 | | private Func<IUpdatablePriorityQueue<int>> PriorityQueueBuilder { get; } |
| | | 48 | | |
| | | 49 | | /// <inheritdoc cref="DijkstraShortestDistanceTreeFinder"/>. |
| | | 50 | | /// <param name="priorityQueueBuilder"> |
| | | 51 | | /// A builder of a <see cref="IUpdatablePriorityQueue{T}"/> of <see cref="int"/> values, used by the algorithm to |
| | | 52 | | /// store edges with priority from the closest to the start, to the farthest. |
| | | 53 | | /// </param> |
| | 14 | 54 | | public DijkstraShortestDistanceTreeFinder(Func<IUpdatablePriorityQueue<int>> priorityQueueBuilder) |
| | 14 | 55 | | { |
| | 14 | 56 | | PriorityQueueBuilder = priorityQueueBuilder; |
| | 14 | 57 | | } |
| | | 58 | | |
| | | 59 | | /// <inheritdoc path="//*[not(self::remarks)]"/> |
| | | 60 | | /// <remarks> |
| | | 61 | | /// <inheritdoc cref="DijkstraShortestDistanceTreeFinder"/> |
| | | 62 | | /// </remarks> |
| | | 63 | | public BestPreviouses FindTree(IGraph graph, IGraphDistances distances, int start) |
| | 14 | 64 | | { |
| | 14 | 65 | | ShortestDistanceFinderHelper.ValidateParameters(graph, start, null); |
| | | 66 | | |
| | 14 | 67 | | var bestPreviouses = new BestPreviouses(new() { [start] = new(0, -1) }); |
| | 14 | 68 | | var added = new HashSet<int>() { start }; |
| | 14 | 69 | | var vertexes = PriorityQueueBuilder(); |
| | 14 | 70 | | var numberOfVertices = graph.GetNumberOfVertices(); |
| | 76 | 71 | | var distancesFunc = (int edgeStart, int edgeEnd) => distances[(edgeStart, edgeEnd)]; |
| | | 72 | | |
| | 14 | 73 | | var lastAdded = start; |
| | 59 | 74 | | while (added.Count < numberOfVertices) |
| | 58 | 75 | | { |
| | 58 | 76 | | ShortestDistanceFinderHelper.RelaxOutgoingEdgesOfVertex( |
| | 58 | 77 | | graph, distancesFunc, bestPreviouses, added, vertexes, lastAdded); |
| | | 78 | | |
| | 55 | 79 | | if (vertexes.Count == 0) |
| | 10 | 80 | | break; |
| | | 81 | | |
| | 45 | 82 | | lastAdded = vertexes.Pop().Item; |
| | 45 | 83 | | added.Add(lastAdded); |
| | 45 | 84 | | } |
| | | 85 | | |
| | 11 | 86 | | return bestPreviouses; |
| | 11 | 87 | | } |
| | | 88 | | } |