Given a non-oriented weighted graph that contains many nodes, how to calculate a subset of the shortest path of all pairs?
A subset means some of the nodes in the graph, and not all of them (a subset of the vertices of the graph can be assigned manually or from some clustering algorithm. The number of selected vertices can be 1% ~ 5% of all vertices).
Any of Dijkstra or Floyd-Warshall can calculate additional nodes, which may not be efficient enough for my application.
Are there algorithms that calculate the entire short path of a pair between specific nodes and provide good performance?
source
share