0
$\begingroup$

Suppose we have a graph with vertices from 1 to n.The graph is undirected and the starting point is 1 and we have path from 1 to any other vertex.We also have positive weight on each edge and there are two types of edges - black and red. The black edges are in the form (1,x) where x is a vertex and red edges can be any pair (x,y) .My question is how can I find the maximum number of black edges I can remove so that the minimal distance from 1 to any other vertex is preserved?

$\endgroup$
  • $\begingroup$ Please add a reference to the original source of the problem. $\endgroup$ – Apass.Jack Jan 12 at 17:42
  • $\begingroup$ Suppose there is a black edge $(1,x)$, do you want the minimum distance from 1 to $x$ preserved? $\endgroup$ – xskxzr Jan 13 at 7:06
0
$\begingroup$

Your graph has no negative edges, then you can do a full exploration using Dijkstra algorithm starting from node 1. You stop when you have explored all nodes. Just record every black edges you cross.

An important point is, when you have several equal distances on a step, always give priority to red edges.

$\endgroup$

Your Answer

By clicking "Post Your Answer", you acknowledge that you have read our updated terms of service, privacy policy and cookie policy, and that your continued use of the website is subject to these policies.

Not the answer you're looking for? Browse other questions tagged or ask your own question.