Conversation

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>