Shortest past including an edge from a given set I am working on the following problem.

There are N vertices and M roads connecting them. Some of the roads are broken. I have to go from vertex 1 to vertex N taking at least one good road and find the minimum number of broken roads taken. If no good road is taken, display &minus;1.

I am trying to use Dijkstra shortest path algorithm for this. I have assigned weight 0 to the good roads and 1 to broken roads. Then I find the shortest path taken. According to me, this shortest path should be equal to the minimum number of broken roads taken. For considering the case where all the roads are broken, I check if the total weight of path is equal to the number of roads taken, then display &minus;1. But I understand, this algorithm will not work always.

What would be the right approach for this problem?
Create two copies of your graph. The first copy represents not having taken a good road, and the second copy represents having taken a good road. You transfer between the copies by taking a good road. The weighting scheme you describe will result in minimizing the number of broken roads. Details left to you.