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