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 −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 −1. But I understand, this algorithm will not work always.
What would be the right approach for this problem?