# Removing max number of edges while keeping minimum distances

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?

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