Here is a 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 

Follow

@Absinthe

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).

@khird okay, so that is. What length means. I will look at it deeper and maybe ask some other quesrions

Sign in to participate in the conversation
Qoto Mastodon

QOTO: Question Others to Teach Ourselves. A STEM-oriented instance.

No hate, No censorship. Be kind, be respectful

We federate with all servers: we don't block any servers.