ShortestGraphPathsC function

Shortest GraphPaths = geodesic distances

Shortest GraphPaths = geodesic distances

Dijkstra's SSSP (Single source shortest path) algorithm, from all points to all points

ShortestGraphPathsC(Adj, Cost)

Arguments

  • Adj: [1:n,1:n] 0/1 adjascency matrix, e.g. from delaunay graph or gabriel graph
  • Cost: [1:n,1:n] matrix, distances between n points (normally euclidean)

Details

Vertices are the points, edges have the costs defined by weights (normally a distance). The algorithm runs in runs in O(nELog(V)), see also [Jungnickel, 2013, p. 87]. Further details can be foubd in [Jungnickel, 2013, p. 83-87] and [Thrun, 2018, p. 12].

Returns

ShortestPaths[1:n,1:n] vector, shortest paths (geodesic) to all other vertices including the source vertice itself from al vertices to all vertices, stored as a matrix

References

[Dijkstra,1959] Dijkstra, E. W.: A note on two problems in connexion with graphs, Numerische mathematik, Vol. 1(1), pp. 269-271. 1959.

[Jungnickel, 2013] Jungnickel, D.: Graphs, networks and algorithms, (4th ed ed. Vol. 5), Berlin, Heidelberg, Germany, Springer, ISBN: 978-3-642-32278-5, 2013.

[Thrun/Ultsch, 2017] Thrun, M.C., Ultsch, A.: Projection based Clustering, Conf. Int. Federation of Classification Societies (IFCS),DOI:10.13140/RG.2.2.13124.53124, Tokyo, 2017.

[Thrun, 2018] Thrun, M. C.: Projection Based Clustering through Self-Organization and Swarm Intelligence, doctoral dissertation 2017, Springer, Heidelberg, ISBN: 978-3-658-20539-3, tools:::Rd_expr_doi("10.1007/978-3-658-20540-9") , 2018.

Author(s)

Michael Thrun

See Also

DijkstraSSSP

Note

require C++11 standard (set flag in Compiler, if not set automatically)

  • Maintainer: Michael Thrun
  • License: GPL-3
  • Last published: 2024-06-20