Which edge do we select when there are multiple direct edges between two points ---- the first one or the one with smaller weights?
computer science
Description
Q: Which edge do we select when there are multiple direct edges between two points ---- the first one or the one with smaller weights? Ans: Assume input graph has no multiple direct edges between 2 vertices. In case such a situation arise during processing, choose one with smallest weight. In input u to v if edge weight is w1 and then again there is mentioned an edge from u to v but with different edge weight value w2, then chose only one value i.e. min (w1,w2) As such in input test cases, we would try not to give you any such case
Q: What are we supposed to do if a vertex is unreachable from the source ----as according to the
definition of arborescence (given in slides) it is possible to reach every vertex by at least one way?
or say, Q: Can you tell if it is okay to assume that the test cases you will provide have the following
property : Every node is reachable from the source node.
Ans: Find min cost (partial) arborescence for the set of vertices that are reachable from given input source
vertex. Mention -1 (unreachable) for other vertices.
Output format remains same i.e. having 2N+1+1 entries. But presence of -1 in output would indicate some
vertices were unreachable.
Q: According to the definition of the min-cost arborescence (given in slides) no negative edge weight,
is there any possibility of having an edge of negative weight in our test cases?
Ans: Safely assume no negative edge weights. We won't give you graph with negative edge weight. If any input
test case does contain any negative edge weight, just output single entry i.e. -1 corresponding to that test case
