Interface IShortestDistanceTreeFinder

An algorithm that, given a start vertex on a weighted directed graph, finds the shortest distance from the start to any other vertex in the graph, and a path for each vertex of the graph having such a total distance.

Namespace: MoreStructures.Graphs.ShortestDistanceTree
Assembly: MoreStructures.dll
Syntax
public interface IShortestDistanceTreeFinder
Remarks

It differs from IShortestDistanceFinder and its implementation in this class of algorithms finds the shortest distance from all vertices of the graph, whereas IShortestDistanceFinder algorithms find the distance between the provided couple of vertices only.
IShortestDistanceFinder implementations can provide the best performance when the shortest distance search is between two fixed points.
If shortest distance has to be found from (or to) a given vertex to any other vertex, the class of algorithms implementing IShortestDistanceTreeFinder can provide better performance, since all distances are computed in a single execution of the algorithm.

Methods

| Improve this Doc View Source

FindTree(IGraph, IGraphDistances, Int32)

Finds the shortest distance and path in the provided graph from the start vertex to each vertex of the graph, 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 to the vertex.

Declaration
BestPreviouses FindTree(IGraph graph, IGraphDistances distances, int start)
Parameters
Type Name Description
IGraph graph

The graph to traverse.
IGraphDistances distances

A map between each edge of graph and its distance.
System.Int32 start

The id of the vertex, to start traversal from.
Returns
Type Description
BestPreviouses

A BestPreviouses instance, wrapping a dictionary, mapping:

  • the id of each vertex v of the graph
  • to the shortest distance S from start,
  • and to the id of the vertex preceeding v on a path from start to v having total distance S.
    This represents a tree T of v' vertices and v' - 1 edges, where v' is at most v, if graph is connected, and strictly lower, if graph has multiple connected components.
    The tree T is rooted in start and its edges are weighted by the distance of the edges minimizing the total distance from the root.
    The distance over a path from the root start to any node of the tree v is the shortest distance from start to v, over a directed path of the graph.

Extension Methods