best path for sewer design

Question

Is there any algorithm(s) that can find all the paths, between a source and a sink, in a given connected, undirected, weighted graph / network? The network consists of multiple source nodes and a single sink node. The path should be free of loops

Answer 1

I would approach this with an A* algorithm with the following differences to basic path finding.

• Start from the sink instead of from source, as there is only one sink
• Each node is a set of positions instead of a single position. In each iteration add the neighbours of all positions to the queue. Also create branches for all the neighbours such that there will be one more position in the next set. Limit the maximum number of positions to the number of sources as an optimization.
• Keep track of which sources you have reached in each path
• The traveled cost function should be the total traveled distance with all the branched paths combined
• The estimate function should combine all the remaining sources

This should give the optimal paths if the A* algorithm is used correctly.

Answer 2

If you look for all loop-free pathes, a breadth-frist search should do the job. In the iteration, for each current path, do not continue it whenever it hits a point already on the path or the sink.

Answer 3

It looks similar to a Minimum Spanning Tree.