Class

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.

Inheritance

System.Object

Implements

System.IEquatable<MoreStructures.Graphs.ShortestDistance.>

Inherited Members

System.Object.Equals(System.Object)

System.Object.Equals(System.Object, System.Object)

System.Object.GetHashCode()

System.Object.GetType()

System.Object.MemberwiseClone()

System.Object.ReferenceEquals(System.Object, System.Object)

System.Object.ToString()

Namespace: MoreStructures.Graphs.ShortestDistance

Assembly: MoreStructures.dll

Syntax

public class  : IEquatable<>

Remarks

Given:

• a starting vertex s and another vertex v, both from the set of vertices V of a graph G,
  
• and a mapping from V to the corresponding MoreStructures.Graphs.ShortestDistance.BestPrevious estimate of shortest path from s,
  the full path is enough to reconstruct the entire path from v to s.
  
  That is thanks to the following properties of optimal paths:
  
• given a correct mapping from vertices to optimal paths for a shortest path, BP;
  
• given an optimal path Pv from s to v, where u = BP[v].PreviousVertex is the immediate predecessor of v in Pv;
  
• given an optimal path Pu from s to u, where w = BP[u].PreviousVertex is the immediate predecessor of u in Pu;
  
• given the path Pu' = Pv - (u, v), with Pu is different Pu';
  Then:
  
• the path Pu', although different than Pu, is also an optimal path from s to u;
  
• the path Pv' = Pu union (u, v), although different than Pv, is also an optimal path from s to v.
  
  That is, sub-paths of optimal paths are also optimal, and replacing a sub-path in an optimal path by a different optimal sub-path yiels a path different than the initial one, yet optimal.

Implements

System.IEquatable<T>

Extension Methods

SuffixStructureNodeExtensions.GetAllSuffixesFor<TEdge, TNode>(TNode, TextWithTerminator)