Nrthugu

I have a graph with one origin and multiple destinations. I'm trying to find a way to word the problem to find the correct type of algorithm to solve. The goal is to have as few paths as possible to reach all of the points, yet the paths must follow grid points at all times (ie, right angles).

For example:

Origin:  (0, 0)

Point A: (3, 3)

Point B: (3, 0)

Point C: (1, 3)

A path from Origin -> C -> A is great because getting to point A only requires 2 extra segments because it was able to share the path from Origin -> C.

Some things I have thought through:

• Exhausting all path options to all points and then exhaustively trying all combinations. This is obviously the brute force and slowest method. Doesn't scale well.


• Creating a matrix of 1's from Origin to Point _, then performing matrix addition in order to find the highest traffic points. Then re-performing some type of exhaustive search, having a preference for those paths which follow the high-traffic segments.

What I would love to do is draw the "top" ways to get to each point from the origin, and then compare each path to each other path to see where they could share paths. This feels recursively tricky.

So, my question is less looking for an answer to the specific problem, and more trying to figure out how to approach the problem, ie, which path (pun intended) to go down when trying to solve.

Overall, looking to score paths based on (no particular order yet):

• Number of segments shared vs unique segments


• Number of turns (preferring straight lines)


• Shortest distance

This does not seem similar to minimal spanning tree, but to Steiner tree, https://en.wikipedia.org/wiki/Steiner_tree_problem in particular rectilinear Steiner tree.

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

Unfortunately that is NP-hard.

Since you can actually reach all points from any point on 2D-space, then you can represent it as a complete graph with N nodes and N * (N - 1) / 2 edges - from each point to all others.

The weight of every edge can express the distance between two nodes, which is equal to the the distance between this points by x plus distance by y, because you only use right angles:

W[a, b] = = |a.x - b.x| + |a.y - b.y|

Now, you have a normal graph, represented by the set of nodes and edges and you can apply any desired algorithms.

It is pretty unclear what score exactly you want to achieve, but building the minimal spanning tree sounds like the answer to the most optimal paths problem.

For example, you can use Kruskal's algorithm to achieve it.