Interface IPotentialBasedShortestDistanceFinder
A IShortestDistanceFinder conceptual extension which introduces a potential function heuristic, to better drive the exploration of vertices of the graph, when searching for the end vertex.
Inherited Members
Namespace: MoreStructures.Graphs.ShortestDistance
Assembly: MoreStructures.dll
Syntax
public interface IPotentialBasedShortestDistanceFinder : IShortestDistanceFinderRemarks
DEFINITION
In order for the potential function to be correct and possibly improve (and not decrease) algorithm
performance, the function P should have a few properties. Some are mandatory, some are recommended.
listed below.
- It must be deterministic, i.e. an actual matematical function, yielding the same output for a
given input, every time it is called.
- It must be feasible, i.e. it should not make distances negative when applied to edge distances on
the graph, if Dijkstra is used as shortest path finder. If distances become negative, Dijkstra
cannot be applied, as its main requirement would be broken.
Notice how it is not enough for the potential function to be non-negative, since the distance d(u, v) of
an edge (u, v) of the graph is shifted by the potential difference, i.e. by P(v) - P(u), which can be
negative and can make the overall edge cost, d(u, v) + P(v) - P(u), negative.
- It should be quick to calculate the potential, not to have an impact on the overall runtime of the
algorithm. Tipically O(1).
- It should be minimal at the end vertex, so that Dijkstra would be incentivized to go towards that
direction, while exploring the graph.
- It should become higher as the distance from the end vertex increases, so that Dijkstra would be
disincentivized from getting farther from the end vertex.
- It tipically is defined as a lower bound for the shortest distance: e.g. the euclidean distance on
the map in a road network.
Methods
| Improve this Doc View SourceFind(IGraph, IGraphDistances, Func<Int32, Int32>, 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, Func<int, int> potentials, int start, int end)Parameters
| Type | Name | Description |
|---|---|---|
| IGraph | graph | |
| IGraphDistances | distances | |
| Func<System.Int32, System.Int32> | potentials | A function mapping each vertex of the provided graph to a System.Int32, providing an heuristic for
"how far" the vertex is from the end vertex, to drive the IPotentialBasedShortestDistanceFinder
towards an earlier, rather than late, discovery of the end vertex.
|
| System.Int32 | start | |
| System.Int32 | end |
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 |