Class DijkstraShortestDistanceFinder
A IShortestDistanceFinder implementation based on the Dijkstra algorithm.
Inheritance
Implements
Inherited Members
Namespace: MoreStructures.Graphs.ShortestDistance
Assembly: MoreStructures.dll
Syntax
public class DijkstraShortestDistanceFinder : IShortestDistanceFinderRemarks
REQUIREMENTS
- Dijkstra algorithm relies on the constraint that edge distances are non-negative. Therefore, there
can't be negative loops and adding edges will always result in longer distances. If the graph has negative
edges, consider using BellmanFordShortestDistanceFinder instead.
- Moreover, given that the path P between two vertices u and v is optimal (i.e. the sum of distances over the
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
sub-path P2, from w to v are optimal.
- The algorithm takes advantage of that, by starting from the start vertex s and finding the shortest distance
for a single vertex v per iteration: the one minimizing the total distance from the start vertex, via any of
the vertices for which the shortest distance has already been calculated.
- The vertex processed at each iteration v may not be in the optimal path from s to e. However, the optimal
path from s to v is surely optimal.
- If e is reachable from s, it will be reached at some point in the traversal. Otherwise, the visit will stop
and a System.Int32.MaxValue distance will be returned instead.
ALGORITHM
- A dictionary BP, mapping each vertex to its currently known shortest distance from the start and the previous
vertex in a path with such a distance is instantiated and initialized to only contains the start vertex s,
which is a distance 0 from itself via an empty path.
- A set A of already added vertices is also instantiated and initialized to only contain s.
- A priority queue PQ, storing ids of not yet added vertices by their known shortest total distance from s, is
also instantiated empty.
- Then, the main loop of the algorithm is executed, until e is not in A.
- Neighbors of the last vertex added to A, named hereafter lav, which are not yet in A, are discovered via
GetAdjacentVerticesAndEdges(Int32, Boolean) and iterated over.
- If the distance d1, of a neighbor v from s via lav, is strictly smaller than the shortest distance from s to
a known by BP, d2, both BP and PQ are updated with the new distance (PQ is updated via
PushOrUpdate<T>(IUpdatablePriorityQueue<T>, T, Int32)).
- After all the neighbors of lav have been processed, the closest vertex to s non-in A is extracted via a
Pop() on PQ, if such a vertex exists.
- If it does exist, such vertex is added to A and becomes the new lav. Otherwise, the loop is stopped.
- After the loop terminates, if e is in BP, it means that a path, which is also shortest, from a to e has been
found, and can be reconstructed backwards by jumping links in BP.
- Otherwise no path from s to e exists in the graph, and System.Int32.MaxValue and an empty path are
returned as a result.
COMPLEXITY
- Initializations of the three data structures BP, A and PQ take a constant amount of work.
- Each iteration in the main loop adds a new vertex to A, and only vertices not yet in A are processed.
- Therefore, the number of iterations in the main loop is at most the number v of vertices in the graph.
- At each iteration all edges outgoing from v are checked.
- Because in the worst case all vertices of the graph need to be explored, to find the shortest distance to e,
the number of edges explored in total can be as high as the total number of edges e in the graph.
- For each edge for which a shortest distance is found (in the worst case all e edges of the graph), both BP
and PQ have to be updated with the new shortest distance.
- Updating BP is done in O(1). Updating PQ, however, has a complexity which depends on the specific
IUpdatablePriorityQueue<T> implementation used.
- As an example, if a BinaryHeapPriorityQueue<T> is used, updating PQ
has logarithmic complexity over the number of items in PQ, which is at most v. So the processing of all
edges, across all iterations, takes time proportional to e * log(v).
- Moreover, after all neighbors of each vertex are processed, a Pop() is done on
PQ, to find the next vertex to add to A. This operation too is logarithmic with the number of items in PQ.
So the total cost of all pop operations, across all iterations, takes time proportional to v * log(v).
- Therefore, when using a BinaryHeapPriorityQueue<T>, Time Complexity
is O((v + e) * log(v)) and Space Complexity is O(v), since all structures contain at most v items, of
constant size.
- The Time Complexity may change when a different IUpdatablePriorityQueue<T> is used.
For instance, if a FibonacciHeapPriorityQueue<T> is used, because
push and update operations are done in constant amortized time, the complexity is reduced to
O(e + v * log(v)), whereas when a ArrayListPriorityQueue<T> is used,
the complexity increases to O((v + e) * v).
Constructors
| Improve this Doc View SourceDijkstraShortestDistanceFinder(Func<IUpdatablePriorityQueue<Int32>>)
Declaration
public DijkstraShortestDistanceFinder(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 SourceFind(IGraph, IGraphDistances, Int32, Int32)
Declaration
public (int, IList<int>) Find(IGraph graph, IGraphDistances distances, int start, int end)Parameters
| Type | Name | Description |
|---|---|---|
| IGraph | graph | |
| IGraphDistances | distances | |
| System.Int32 | start | |
| System.Int32 | end |
Returns
| Type | Description |
|---|---|
| System.ValueTuple<System.Int32, IList<System.Int32>> |