Follow

Here is a #toyprogrammingchallenge which corresponds to the general case of a problem I ran up against recently.

Given a positive integer K and a directed graph G with weighted edges, return a new graph H satisfying all the following conditions, if such a graph exists:

1. G and H contain exactly the same set of vertices.

2. H contains only edges in G, but G may contain edges not in H.

3. A path exists in H of length at most K between each pair of vertices in each direction.

4. No edge can be removed from H while still satisfying condition 3.

Where more than one graph exists satsifying these conditions, return the one with the least total weight. You may assume G does not contain edges with negative weights.

Here is an example G, each triplet representing the <start, end, weight> of an edge:

<1, 2, 40>

<1, 3, 12>

<1, 4, 50>

<2, 1, 84>

<2, 3, 19>

<2, 4, 69>

<3, 1, 25>

<3, 2, 78>

<3, 4, 93>

<4, 1, 75>

<4, 2, 36>

<4, 3, 96>

Your program should produce the following H given the above G and K = 2:

<1, 2, 40>

<1, 4, 50>

<2, 1, 84>

<2, 3, 19>

<3, 1, 25>

<4, 2, 36>

La Fée Verte@Absinthe@qoto.orgdiscussion of the problem

@khird I have never done anything with digraphs nor really studied graph theory and so I am not really sure I am equipped to handle this challenge. However, let me ask a few things and perhaps I will learn something. Given that you have an edge <x, y, z> if there is another edge <y, x, z> either one could be removed without affecting the vertices? Or does a vertex need at least one start point and one end point? Looking at the example, it would have seemed the solution should have excluded <2,1,84> as it already had <1,2,40> because it doesn't affect the vertices but reduces the count. Is there an issue with "length" that I am not quite sure I follow?