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.

$\endgroup$
  • $\begingroup$ What now, shortest paths or MST? The two are not the same. $\endgroup$ – Raphael Jun 28 '18 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 '18 at 5:33
  • $\begingroup$ I updated the question with some extra explanation. $\endgroup$ – Francis Jun 28 '18 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 '18 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 '18 at 15:16
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.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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