How to use Prims algorithm in 3d space

Question

I was wondering how I could use Prim's algorithm in 3d space. To put it into context: I want to calculate all possible and the shortest/most efficient way/s to lay a cable in a wall with considering some unusable spots/constraints in 3d space.

Any ideas how it could modeled (algorithmically as well as technically)? I do know common shortst path and min/max spanning tree algorithms but learned/used them just in 2d space till now.

Answer 1

You should simply convert your 3D wall to a graph. Let's say our wall is a simple cube, we divide it into many small cubes:

For every intersection you create a new vertex in your graph and for each line between intersections you create a new edge in your graph.

Since you end up with a regular graph, you can use Prim's algorithm.

You can omit vertices and edges where the obstructions are and decrease the size of the cubes if you want a higher granularity.