I would like to know if there is a natural way of transforming a graph in which one seeks the shortest path between two nodes into a riemannian manifold whose this graph is a subspace. My idea is to consider the distance between two consecutive nodes of a graph $ G $ as a variable $ h(G) $ and to build a sequence of graphs $ (G_{n})_n $ such that $ G_0=G $ and for all $ i\leq j $ $ G_i $ is a subgraph of $ G_j $, with $ h(G_n) $ a decreasing function of $ n $ tending to $ 0 $ as $ n $ tends to infinity and $ G_n $ tending to a bounded domain of a riemannian manifold, its metric tensor being in some sense the limit of the weights between adjacent nodes. That way the shortest path between nodes $ A $ and $ B $ in $ G_n $ tends to the geodesic joining $ A $ and $ B $ in the limit manifold. One can process backwards and from this manifold determine the considered geodesic solving the geodesic equation and recover the shortest path in $ G_n $ for any given $ n $ as a sequence of points of this geodesic that belong to $ G_n $. In this framework, can the principle of stationary action lead to an optimal algorithm to find the shortest path in a graph ?

Has this been considered before ? If yes, could I get some reference ?

  • 1
    $\begingroup$ Consider the simplest case of a 2D plane. If you make a regular $4$-connected grid of vertices, the graph distance will overestimate the geodesic distance by a factor of $\sqrt 2$ for diagonal paths, and this error does not go away as you refine the grid. $\endgroup$ – Rahul Sep 29 '18 at 13:45
  • $\begingroup$ The lengths of the successive shortest paths and of the geodesic need not be equal but "locally" minimal (in some neighborhood of such points in a space of paths). $\endgroup$ – Sylvain Julien Sep 29 '18 at 14:02
  • $\begingroup$ In your example, the real shortest path in your grid is the closest path therein to the limit geodesic. $\endgroup$ – Sylvain Julien Sep 29 '18 at 14:04
  • $\begingroup$ The grid path closest to the limit geodesic is just one of many shortest paths all having equal length. For example, instead of going alternately one step north and one step east $n$ times, you could go north $n$ steps and then east $n$ steps. $\endgroup$ – Rahul Sep 29 '18 at 17:47
  • $\begingroup$ You can probably avoid this by placing vertices randomly according to e.g. a Poisson point process. There appear to be some work on routing on point processes (e.g. Baccelli et al 1998) and shortest paths through random points which seems relevant. $\endgroup$ – Rahul Sep 29 '18 at 17:48

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Browse other questions tagged or ask your own question.