Class BellmanFordShortestDistanceFinder
An IShortestDistanceFinder implementation based on the Bellman-Ford algorithm.
Inheritance
Implements
Inherited Members
Namespace: MoreStructures.Graphs.ShortestDistance
Assembly: MoreStructures.dll
Syntax
public class BellmanFordShortestDistanceFinder : IShortestDistanceFinderRemarks
ADVANTAGES AND DISADVANTAGES
- Unlike DijkstraShortestDistanceFinder, this implementation doesn't require distances to be
non-negative and it also works in presence of negative cycles.
- Unlike DijkstraShortestDistanceFinder, this algorithm doesn't require any external data
structure (such as a IPriorityQueue<T> implementation: its runtime performance
solely depends on the algorithm itself.
- However, due to the generality of conditions in which it operates, it can't leverage the same performance as
the Dijkstra algorithm. So, if the graph doesn't have negative distances, or it can be reduce not to have
them, consider using DijkstraShortestDistanceFinder instead, for better performance.
- In particolar it has a quadratic performance, instead of the linearithmic Time Complexity of Dijkstra on
graphs with non-negative distances or the linear complexity of "edge relaxation in topological order" on
DAGs.
ALGORITHM
- As in the Dijkstra 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.
- Then BP is initialized to only contains the start vertex s, which is a distance 0 from itself via an empty
path.
- After that, the main loop of algorithm is executed v times, where v is the number of edges in the graph.
- At each iteration, all the edges in the graph are visited and relaxed.
- Edge (u, v) relation is done in the following way: if the distance of u from s in BP is not defined, it is to
be considered as +Infinity. Therefore, there is no viable path from s to v via u, and no relation is
possible via the edge (u, v).
- If the distance BP[u].d of u from s in BP is defined instead, but the distance of v from s in BP is not,
the path going from s to v via u becomes the shortest knows, and is set into BP[v].
- If both distances BP[u].d and BP[v].d of u and v from s in BP are defined, there are two possible cases.
- Either BP[v].d is non-bigger than BP[u].d + the distance of (u, v), in which case the edge (u, v) won't
decrease the current estimate of the shortest path from s to v and won't be relaxed.
- Or BP[v].d is strictly bigger, in which case the edge (u, v) does decrease the currently known shortest path
from s to v, and will be relaxed, updating BP[v].
- After v - 1 iterations, all edges are fully relaxed if there are no negative cycles.
- To check whether that's the case, a last, v-th iteration, is performed. If no edge is relaxed, there are no
negative cycles. Otherwise, there are. The set VR, of target vertices of edges relaxed at the v-th iteration,
is stored.
- If there are negative cycles, each vertex v in VR, and each vertex reachable from v, has -Infinite distance
from the start. So a DFS is executed on the graph for each v in VR, and BP is updating, setting BP[v].d
to -Infinity and BP[v].previousVertex to null (since there is no actual finite shortest path).
- If the end vertex is at a finite distance from the start, BP[e] contains such shortest distance, and the
shortest path can be found by backtracking on previous pointers via BP, from e all the way back to s.
- Otherwise -Infinity or +Infinity is returned, with an empty path, because either no path exists from the
start to the end, or a path exists, but the shortest is infinitely long.
COMPLEXITY
- BP initialization is done in constant time.
- The main loop of the algorithm is performed v times.
- Each iteration checks and possibly relaxes all e edges of the graph. A single graph relation requires
checking values in BP and edge distances, which are all constant-time operations.
- Retrieving all e edges has a complexity which is specific to the IGraph implementation: in a
EdgeListGraph it is a O(1) operation, since edges are stored as a flat list.
- In a AdjacencyListGraph it is a O(v) operation, since edges are stored in neighborhoods of the
v vertices.
- In a AdjacencyMatrixGraph it is a O(v^2) operation, as it requires going through the matrix.
- In case the presence of negative cycles is detected, up to r DFS explorations are performed, where r is the
number of vertices in VR (i.e. target of edges relaxed during the v-th iteration of the main loop).
- In the worst case that means work proportional to v * (v + e), when r = v and assuming linear cost for DFS.
- In case there are no negative cycles, up to v more iterations are performed to find the shortest path from
s to e.
- In conclusion Time Complexity is O(v * (v * Tn + e)), where Tn is the time to retrieve the neighborhood of
a single vertex. Space Complexity is O(v + Sn), since BP contain at most v items, of constant size.
Constructors
| Improve this Doc View SourceBellmanFordShortestDistanceFinder(Func<IVisitStrategy>)
Declaration
public BellmanFordShortestDistanceFinder(Func<IVisitStrategy> visitStrategyBuilder)Parameters
| Type | Name | Description |
|---|---|---|
| Func<IVisitStrategy> | visitStrategyBuilder |
Remarks
Properties
| Improve this Doc View SourceVisitStrategyBuilder
A building function able to instantiate the IVisitStrategy to be used to find all reachable vertices of vertices relaxed in the last iteration of the main loop of the Bellman-Ford algorithm, by running a Depth First Searches from the start vertex via DepthFirstSearchFromVertex(IGraph, Int32).
Declaration
public Func<IVisitStrategy> VisitStrategyBuilder { get; }Property Value
| Type | Description |
|---|---|
| Func<IVisitStrategy> |
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>> |