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:
- We pick an arbitrary order nodes, say [1,2,5,0,3,4].
- First we create the cheapest path between two of the nodes, in this case between nodes 1 and 2 using A*.
- 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.
- 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(
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.