Finding the Cheapest path connecting multiple nodes

Question

I have a grid, where I have to connect multiple nodes(cells) with a single branching path (with obstacle cells at different positions). Path is, by nature, bidirectional. Any node can be source or destination, without affecting the problem. I want to connect all the selected nodes with a single cheapest branching path.

Currently, the approach I am using is as follows:

1. We pick an arbitrary order nodes, say [1,2,5,0,3,4].
2. First we create the cheapest path between two of the nodes, in this case between nodes 1 and 2 using A*.
3. Then, we take the third node (in this case 5) and find the cheapest path between the third node and each node of the cheapest path between 1 and 2. Then, we pick the path, which is the shortest among all those paths.
4. We repeat this process until we have a path connecting all the nodes.

The above process is repeated for various such orders till we find the cheapest possible path. However, I feel like this method is very, very suboptimal and there has to be a better way to go about solving this problem.

I also found this particular question(pathfinding with multiple source and sinks?) which is similar but in this case, the output seems to be having multiple paths.But, in my case, I want a single path connecting the selected nodes (branching is allowed). I have a feeling that Dijkstra's algorithm (atleast from my limited understanding of it) might be the one that will work in this case.

Any help(papers or articles) will be much appreciated. Thank you.

Answer 1

I think you are looking for a spanning tree

https://en.wikipedia.org/wiki/Spanning_tree

---

not looking to connect all the nodes, but only few specific nodes among a grid of large number of nodes

• Calculate cheapest path between each pair of specific nodes ( Dijkstra )
• Remove all nodes that are not specific
• Remove all edges
• Add edges between pairs of specific nodes with the cost of the cheapest path between them
• Calculate spanning tree.