| | | 1 | | namespace MoreStructures.Graphs.ShortestDistance; |
| | | 2 | | |
| | | 3 | | /// <summary> |
| | | 4 | | /// Represents the best estimate of the shortest distance of a vertex in a graph, from a given start vertex. |
| | | 5 | | /// Includes the id of the previous vertex, to reconstruct a path of such shortest distance. |
| | | 6 | | /// </summary> |
| | | 7 | | /// <param name="DistanceFromStart"> |
| | | 8 | | /// The shortest distance from the start vertex s to the vertex v. Possibly negative. |
| | | 9 | | /// </param> |
| | | 10 | | /// <param name="PreviousVertex"> |
| | | 11 | | /// The id of the vertex in the graph which preceeds the vertex v, in one of the shortest paths from start to v. |
| | | 12 | | /// <br/> |
| | | 13 | | /// It's negative when the vertex v has no predecessor, because v corresponds to s. |
| | | 14 | | /// </param> |
| | | 15 | | /// <remarks> |
| | | 16 | | /// Given: |
| | | 17 | | /// <br/> |
| | | 18 | | /// - a starting vertex s and another vertex v, both from the set of vertices V of a graph G, |
| | | 19 | | /// <br/> |
| | | 20 | | /// - and a mapping from V to the corresponding <see cref="BestPrevious"/> estimate of shortest path from s, |
| | | 21 | | /// <br/> |
| | | 22 | | /// the full path <see cref="PreviousVertex"/> is <b>enough to reconstruct the entire path</b> from v to s. |
| | | 23 | | /// <br/> |
| | | 24 | | /// <br/> |
| | | 25 | | /// That is thanks to the following properties of optimal paths: |
| | | 26 | | /// <br/> |
| | | 27 | | /// - given a correct mapping from vertices to optimal paths for a shortest path, BP; |
| | | 28 | | /// <br/> |
| | | 29 | | /// - given an optimal path Pv from s to v, where <c>u = BP[v].PreviousVertex</c> is the immediate predecessor of |
| | | 30 | | /// v in Pv; |
| | | 31 | | /// <br/> |
| | | 32 | | /// - given an optimal path Pu from s to u, where <c>w = BP[u].PreviousVertex</c> is the immediate predecessor of |
| | | 33 | | /// u in Pu; |
| | | 34 | | /// <br/> |
| | | 35 | | /// - given the path <c>Pu' = Pv - (u, v)</c>, with Pu is different Pu'; |
| | | 36 | | /// <br/> |
| | | 37 | | /// Then: |
| | | 38 | | /// <br/> |
| | | 39 | | /// - the path Pu', although different than Pu, is also an optimal path from s to u; |
| | | 40 | | /// <br/> |
| | | 41 | | /// - the path <c>Pv' = Pu union (u, v)</c>, although different than Pv, is also an optimal path from s to v. |
| | | 42 | | /// <br/> |
| | | 43 | | /// <br/> |
| | | 44 | | /// That is, sub-paths of optimal paths are also optimal, and replacing a sub-path in an optimal path by a |
| | | 45 | | /// different optimal sub-path yiels a path different than the initial one, yet optimal. |
| | | 46 | | /// </remarks> |
| | 60801 | 47 | | public record struct BestPrevious(int DistanceFromStart, int PreviousVertex); |