2
$\begingroup$

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?

Improve this question
$\endgroup$
5
  • $\begingroup$ Welcome to CS.SE! It sounds like you're asking us to solve your exercise for you. We're happy to help you understand the concepts but just solving exercises for you is unlikely to achieve that. You might find this page helpful in improving your question. You have an attempt at a solution, which looks like a good first start. Which of the requirements does your attempt meet, and which does it not meet? Can you think of any way to fix up the latter? How many possibilities are there for the good road that's taken? $\endgroup$
    – D.W. ♦
    Commented Mar 5, 2017 at 13:59
  • $\begingroup$ Also, check the requirement "If no good road is taken, display -1." - I suspect you haven't gotten that quite right. The previous sentence says you have to use at least one good road, so I suspect you probably mean something like "if it's not possible to go from vertex 1 to vertex N taking at least one good road, return -1". $\endgroup$
    – D.W. ♦
    Commented Mar 5, 2017 at 14:01
  • 2
    $\begingroup$ Cross-posted: cs.stackexchange.com/q/71157/755, stackoverflow.com/q/42606479/781723. Please do not post the same question on multiple sites. Each community should have an honest shot at answering without anybody's time being wasted. $\endgroup$
    – D.W. ♦
    Commented Mar 5, 2017 at 14:03
  • 1
    $\begingroup$ Your idea can be modified to work by using more extreme weights. There are other approaches which track more carefully whether you have already taken a good road or not. I suggest spending a few more hours on the question. $\endgroup$
    – Yuval Filmus
    Commented Mar 5, 2017 at 16:22
  • $\begingroup$ Welcome to Computer Science! The title you have chosen is not well suited to representing your question. Please take some time to improve it; we have collected some advice here. Thank you! $\endgroup$
    – Raphael
    Commented Mar 5, 2017 at 16:51

1 Answer 1

Reset to default
1
$\begingroup$

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.

Improve this answer
$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.