This paper presents a novel framework for finding the shortest path for all pairs on a manifold with a metric defined as infinitesimal. This framework generates shortest paths by recursively predicting midpoints. We propose an actor-critic approach for midpoint prediction, and experimentally demonstrate the validity of the proposed method, outperforming existing methods on several planning tasks, including path planning for agents with complex kinematics and motion planning for multi-degree-of-freedom robot arms.