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>
discussion 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?
Think of edges in a directed graph as arrows, which you can follow in the direction they point but not in the opposite direction. The edge <1, 2, 40> allows you to go *from* node 1 *to* node 2, while <2, 1, 84> allows you to go *to* node 1 *from* node 2. So if you exclude the edge you suggested, the graph no longer satisfies the third condition (k-hop rule) because it's no longer possible to get from node 4 to node 1 in two hops (shortest path is 4->2->3->1, which is three hops).
