Interface IShortestDistanceFinder
An algorithm that, given starting and ending vertices on a weighted directed graph, finds the shortest distance from the start to the end vertex, and a path on the graph having such a total distance.
Namespace: MoreStructures.Graphs.ShortestDistance
Assembly: MoreStructures.dll
Syntax
public interface IShortestDistanceFinderRemarks
It differs from IShortestPathFinder and its implementation because this class of
algorithms takes into account weight of edges (i.e. distances between vertices).
By contrast, the class of algorithm implementing IShortestPathFinder only takes into
account presence or absence of an edge: i.e. each edge is weighted "1", and vertex v is at distance 1 from vertex u
if there is a direct edge from v to u, and at distance infinity, if there is no path from v to u.
Methods
| Improve this Doc View SourceFind(IGraph, IGraphDistances, Int32, Int32)
Finds the shortest distance and path in the provided graph from the start
vertex to the end vertex, i.e. a path such that the sum of distances of all the edges on the
path is non-bigger than the one of any other path from the provided start and
end vertices
Declaration
(int, IList<int>) Find(IGraph graph, IGraphDistances distances, int start, int end)Parameters
| Type | Name | Description |
|---|---|---|
| IGraph | graph | The graph to traverse. |
| IGraphDistances | distances | A map between each edge of |
| System.Int32 | start | The id of the vertex, to start traversal from. |
| System.Int32 | end | The id of the vertex, to end traversal at. |
Returns
| Type | Description |
|---|---|
| System.ValueTuple<System.Int32, IList<System.Int32>> | A couple. The first item of the couple is the shortest distance, as the sum of the distance of each edge of the
shortest path between |