Namespace MoreStructures.Graphs.ShortestDistance

Classes

MoreStructures.Graphs.ShortestDistance.

Represents the best estimate of the shortest distance of a vertex in a graph, from a given start vertex. Includes the id of the previous vertex, to reconstruct a path of such shortest distance.

AStarShortestDistanceFinder

A IShortestDistanceFinder implementation based on the A* algorithm, which is a refinement of the Dijkstra's algorithm, introducing a goal-oriented heuristic, driving the search in the direction of the end vertex.

BellmanFordShortestDistanceFinder

An IShortestDistanceFinder implementation based on the Bellman-Ford algorithm.

BestPreviouses

A collection of estimation, indexed by vertex id.

BfsBasedShortestDistanceFinder

An IShortestDistanceFinder which runs a BFS on the provided graph from the start vertex, to find the shortest distance and a shortest path to the end vertex.

BidirectionalAStarShortestDistanceFinder

A IPotentialBasedShortestDistanceFinder implementation based on the bidirectional A* algorithm, which combines the goal-oriented heuristic of the A* algorithm and the double search approach of the bidirectional Dijkstra's algorithm.

BidirectionalDijkstraShortestDistanceFinder

A IShortestDistanceFinder implementation based on a refinement of the Dijkstra algorithm, running search in two parallel inversed flows: from the start vertext to the end vertex and viceversa.

DijkstraShortestDistanceFinder

A IShortestDistanceFinder implementation based on the Dijkstra algorithm.

PotentialBasedShortestDistanceFinder

An IPotentialBasedShortestDistanceFinder implementation, wrapping a IShortestDistanceFinder algorithm and using a potential function as a heuristic to enhance graph exploration.

Interfaces

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.

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.