# 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. – John L. Jan 12 '19 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 '19 at 7:06

## 1 Answer

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.

• Just to complement @Vince's answer, once you compute the shortest path from vertex 1 to any other vertex using Dijkstra (with preference to red edges), you can do the following: For each vertex other than 1, mark all the edges occurring on the shortest path from 1 to that vertex. After you do so for all vertices, you will observe that all edges that have been marked together form a spanning tree. Deleting all unmarked edges will not increase the cost. This is exactly what Vince said, but I thought it may be worthwhile to mention that the marked edges constitute a spanning tree. – csTheoryBeginner Feb 11 '19 at 22:55