2
$\begingroup$

Let's say I have a map with factories and selling points. I want to trace the paths from factories to the selling points with the lower possible cost. The image bellow is an example of a possible solution for that map, then the output of the algorithm should be two trees with the edges of those trees. enter image description here If there is only one factory a possible solution would be using Kruskal's algorithm to find the MST with this factory as source.

¿Is there any algorithm to do so? ¿How would a modification of Kruskal's work?

[EDIT] I need to find the minimum cost tree from factories to shops but given that there is more than one factory may have unconnected trees as optimal solution.

[EDIT 2] If an edge is used twice that cost counts only once.

Improve this question
$\endgroup$
6
  • $\begingroup$ What now, shortest paths or MST? The two are not the same. $\endgroup$
    – Raphael ♦
    Jun 28, 2018 at 5:31
  • $\begingroup$ Please edit the question to clarify what you are asking. Also, it might help to tell us what the inputs to the algorithm are, and what the the desired output is. An example is not enough. We need a specification of the problem. $\endgroup$
    – D.W. ♦
    Jun 28, 2018 at 5:33
  • $\begingroup$ I updated the question with some extra explanation. $\endgroup$
    – Francis
    Jun 28, 2018 at 6:34
  • $\begingroup$ If an edge is used twice, does its cost count only once? Please clarify that in the question. $\endgroup$
    – Gassa
    Jun 28, 2018 at 9:41
  • 1
    $\begingroup$ @Gassa indeed, if you use an edge twice that would only count once. How would the modification be ? should I loop through all factories ? Thanks for the reply ! $\endgroup$
    – Francis
    Jun 28, 2018 at 15:16

1 Answer 1

Reset to default
1
$\begingroup$

Here is a slight modification of Kruskal's algorithm which can solve this.

Sort all edges by non-decreasing weight. Maintain a disjoint set union to track which vertices are connected, as usual. Consider the edges one by one in the resulting order. If an edge connects two vertices which are already connected, we drop it, as usual.

The difference is as follows: if an edge connects two components such that each already contains a factory, such edge would contribute nothing to our network, so we also drop it.

If an edge connects two components, and at least one of them does not contain a factory, we take the edge and update the disjoint set union, as usual.

Another view with the same result is as follows. Make an auxiliary vertex, the super-factory. Add an edge of weight 0 from the super-factory to each of the real factories. Run Kruskal algorithm on this new graph.

First thing, it will take all our added edges with weight 0. If the original graph also had such edges, let the algorithm start with our newly added edges. We can do it since the total cost does not depend on the ordering of same-weight edges.

Now, the original condition “each shop must be connected to a factory” got translated to “each shop must be connected to the super-factory”, which is equivalent to just “all vertices must be connected”, which in turn is exactly what Kruskal algorithm will do for us.

Improve this answer
$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge that you have read and understand our privacy policy and code of conduct.

Not the answer you're looking for? Browse other questions tagged or ask your own question.