< Summary

Information
Class: MoreStructures.Graphs.ShortestDistance.DijkstraShortestDistanceFinder
Assembly: MoreStructures
File(s): /home/runner/work/MoreStructures/MoreStructures/MoreStructures/Graphs/ShortestDistance/DijkstraShortestDistanceFinder.cs
Line coverage
100%
Covered lines: 27
Uncovered lines: 0
Coverable lines: 27
Total lines: 150
Line coverage: 100%
Branch coverage
100%
Covered branches: 6
Total branches: 6
Branch coverage: 100%
Method coverage

Feature is only available for sponsors

Upgrade to PRO version

Metrics

MethodBranch coverage Cyclomatic complexity Line coverage
get_PriorityQueueBuilder()100%1100%
.ctor(...)100%1100%
Find(...)100%6100%

File(s)

/home/runner/work/MoreStructures/MoreStructures/MoreStructures/Graphs/ShortestDistance/DijkstraShortestDistanceFinder.cs

#LineLine coverage
 1using MoreStructures.PriorityQueues;
 2using MoreStructures.PriorityQueues.Extensions;
 3
 4namespace MoreStructures.Graphs.ShortestDistance;
 5
 6/// <summary>
 7/// A <see cref="IShortestDistanceFinder"/> implementation based on the Dijkstra algorithm.
 8/// </summary>
 9/// <remarks>
 10///     <para id="requirements">
 11///     REQUIREMENTS
 12///     <br/>
 13///     - Dijkstra algorithm relies on the constraint that <b>edge distances are non-negative</b>. Therefore, there
 14///       can't be negative loops and adding edges will always result in longer distances. If the graph has negative
 15///       edges, consider using <see cref="BellmanFordShortestDistanceFinder"/> instead.
 16///       <br/>
 17///     - Moreover, given that the path P between two vertices u and v is optimal (i.e. the sum of distances over the
 18///       edges of the path is minimal), if w is a vertex in P, both the sub-path of P, P1, from u and w, and the
 19///       sub-path P2, from w to v are optimal.
 20///       <br/>
 21///     - The algorithm takes advantage of that, by starting from the start vertex s and finding the shortest distance
 22///       for a single vertex v per iteration: the one minimizing the total distance from the start vertex, via any of
 23///       the vertices for which the shortest distance has already been calculated.
 24///       <br/>
 25///     - The vertex processed at each iteration v may not be in the optimal path from s to e. However, the optimal
 26///       path from s to v is surely optimal.
 27///       <br/>
 28///     - If e is reachable from s, it will be reached at some point in the traversal. Otherwise, the visit will stop
 29///       and a <see cref="int.MaxValue"/> distance will be returned instead.
 30///     </para>
 31///     <para id="algorithm">
 32///     ALGORITHM
 33///     <br/>
 34///     - A dictionary BP, mapping each vertex to its currently known shortest distance from the start and the previous
 35///       vertex in a path with such a distance is instantiated and initialized to only contains the start vertex s,
 36///       which is a distance 0 from itself via an empty path.
 37///       <br/>
 38///     - A set A of already added vertices is also instantiated and initialized to only contain s.
 39///       <br/>
 40///     - A priority queue PQ, storing ids of not yet added vertices by their known shortest total distance from s, is
 41///       also instantiated empty.
 42///       <br/>
 43///     - Then, the main loop of the algorithm is executed, until e is not in A.
 44///       <br/>
 45///     - Neighbors of the last vertex added to A, named hereafter lav, which are not yet in A, are discovered via
 46///       <see cref="IGraph.GetAdjacentVerticesAndEdges(int, bool)"/> and iterated over.
 47///       <br/>
 48///     - If the distance d1, of a neighbor v from s via lav, is strictly smaller than the shortest distance from s to
 49///       a known by BP, d2, both BP and PQ are updated with the new distance (PQ is updated via
 50///       <see cref="UpdatablePriorityQueueExtensions.PushOrUpdate{T}(IUpdatablePriorityQueue{T}, T, int)"/>).
 51///       <br/>
 52///     - After all the neighbors of lav have been processed, the closest vertex to s non-in A is extracted via a
 53///       <see cref="IPriorityQueue{T}.Pop"/> on PQ, if such a vertex exists.
 54///       <br/>
 55///     - If it does exist, such vertex is added to A and becomes the new lav. Otherwise, the loop is stopped.
 56///       <br/>
 57///     - After the loop terminates, if e is in BP, it means that a path, which is also shortest, from a to e has been
 58///       found, and can be reconstructed backwards by jumping links in BP.
 59///       <br/>
 60///     - Otherwise no path from s to e exists in the graph, and <see cref="int.MaxValue"/> and an empty path are
 61///       returned as a result.
 62///     </para>
 63///     <para id="complexity">
 64///     COMPLEXITY
 65///     <br/>
 66///     - Initializations of the three data structures BP, A and PQ take a constant amount of work.
 67///       <br/>
 68///     - Each iteration in the main loop adds a new vertex to A, and only vertices not yet in A are processed.
 69///       <br/>
 70///     - Therefore, the number of iterations in the main loop is at most the number v of vertices in the graph.
 71///       <br/>
 72///     - At each iteration all edges outgoing from v are checked.
 73///       <br/>
 74///     - Because in the worst case all vertices of the graph need to be explored, to find the shortest distance to e,
 75///       the number of edges explored in total can be as high as the total number of edges e in the graph.
 76///       <br/>
 77///     - For each edge for which a shortest distance is found (in the worst case all e edges of the graph), both BP
 78///       and PQ have to be updated with the new shortest distance.
 79///       <br/>
 80///     - Updating BP is done in O(1). Updating PQ, however, has a complexity which depends on the specific
 81///       <see cref="IUpdatablePriorityQueue{T}"/> implementation used.
 82///       <br/>
 83///     - As an example, if a <see cref="PriorityQueues.BinaryHeap.BinaryHeapPriorityQueue{T}"/> is used, updating PQ
 84///       has logarithmic complexity over the number of items in PQ, which is at most v. So the processing of all
 85///       edges, across all iterations, takes time proportional to e * log(v).
 86///       <br/>
 87///     - Moreover, after all neighbors of each vertex are processed, a <see cref="IPriorityQueue{T}.Pop"/> is done on
 88///       PQ, to find the next vertex to add to A. This operation too is logarithmic with the number of items in PQ.
 89///       So the total cost of all pop operations, across all iterations, takes time proportional to v * log(v).
 90///       <br/>
 91///     - Therefore, when using a <see cref="PriorityQueues.BinaryHeap.BinaryHeapPriorityQueue{T}"/>, Time Complexity
 92///       is O((v + e) * log(v)) and Space Complexity is O(v), since all structures contain at most v items, of
 93///       constant size.
 94///       <br/>
 95///     - The Time Complexity may change when a different <see cref="IUpdatablePriorityQueue{T}"/> is used.
 96///       For instance, if a <see cref="PriorityQueues.FibonacciHeap.FibonacciHeapPriorityQueue{T}"/> is used, because
 97///       push and update operations are done in constant amortized time, the complexity is reduced to
 98///       O(e + v * log(v)), whereas when a <see cref="PriorityQueues.ArrayList.ArrayListPriorityQueue{T}"/> is used,
 99///       the complexity increases to O((v + e) * v).
 100///     </para>
 101/// </remarks>
 102public class DijkstraShortestDistanceFinder : IShortestDistanceFinder
 103{
 857104    private Func<IUpdatablePriorityQueue<int>> PriorityQueueBuilder { get; }
 105
 106    /// <inheritdoc cref="DijkstraShortestDistanceFinder"/>.
 107    /// <param name="priorityQueueBuilder">
 108    /// A builder of a <see cref="IUpdatablePriorityQueue{T}"/> of <see cref="int"/> values, used by the algorithm to
 109    /// store edges with priority from the closest to the start, to the farthest.
 110    /// </param>
 157111    public DijkstraShortestDistanceFinder(Func<IUpdatablePriorityQueue<int>> priorityQueueBuilder)
 157112    {
 157113        PriorityQueueBuilder = priorityQueueBuilder;
 157114    }
 115
 116    /// <inheritdoc path="//*[not(self::remarks)]"/>
 117    /// <remarks>
 118    ///     <inheritdoc cref="DijkstraShortestDistanceFinder"/>
 119    /// </remarks>
 120    public (int, IList<int>) Find(IGraph graph, IGraphDistances distances, int start, int end)
 877121    {
 877122        ShortestDistanceFinderHelper.ValidateParameters(graph, start, end);
 123
 857124        var bestPreviouses = new BestPreviouses(new() { [start] = new(0, -1) });
 857125        var added = new HashSet<int>() { start };
 857126        var vertexes = PriorityQueueBuilder();
 3339127        var distancesFunc = (int edgeStart, int edgeEnd) => distances[(edgeStart, edgeEnd)];
 128
 857129        var lastAdded = start;
 2868130        while (lastAdded != end)
 2383131        {
 2383132            ShortestDistanceFinderHelper.RelaxOutgoingEdgesOfVertex(
 2383133                graph, distancesFunc, bestPreviouses, added, vertexes, lastAdded);
 134
 2368135            if (vertexes.Count == 0)
 357136                break;
 137
 2011138            lastAdded = vertexes.Pop().Item;
 2011139            added.Add(lastAdded);
 2011140        }
 141
 842142        if (!bestPreviouses.Values.ContainsKey(end))
 357143            return (int.MaxValue, Array.Empty<int>());
 144
 485145        var shortestDistance = bestPreviouses.Values[end].DistanceFromStart;
 485146        var shortestPath = ShortestDistanceFinderHelper.BuildShortestPath(end, bestPreviouses);
 147
 485148        return (shortestDistance, shortestPath);
 842149    }
 150}
Generated by: ReportGenerator 5.1.19.0
03/19/2023 - 17:28:50
GitHub | reportgenerator.io

Methods/Properties

get_PriorityQueueBuilder()
.ctor(System.Func`1<MoreStructures.PriorityQueues.IUpdatablePriorityQueue`1<System.Int32>>)
Find(MoreStructures.Graphs.IGraph,MoreStructures.Graphs.IGraphDistances,System.Int32,System.Int32)