The_mysterio's blog

BFS to find out the shortest path between two given vertices [Solved]
By The_mysterio, history, 3 years ago, In English

The topic of this blog comes from this problem in the link https://codeforces.com/contest/20/problem/C

I decided to apply BFS to find the shortest path from 1 to n. In the internet, I found almost every article saying BFS cannot be applied to find shortest path in a unevenly weighted graph. Well, I am unable to understand why so. I applied the BFS with a little amount of tweak.

  1. Initially when a node is visited, the shortest distance of that node from origin is set as : distance of node from origin=distance of its parent from origin + weight of the edge through which the node is getting discovered.

  2. If we visit a node that has already been visited, then we check whether this new path to the already visited node is shorter than the previous path through which it was visited. If so, then update the shortest distance of the already discovered node from the origin and change the parent accordingly.

This is my code with the above approach :- https://codeforces.com/contest/20/submission/102479947

I am getting wrong answer as you can see. I do not ask you to debug my code. But I want to know isn't my approach valid? I infact feel that this approach can be used to find shortest path to all the nodes from a single vertex instead of using Djikstra.

Any comments???.....

Thanks in advance. Please kindly copy-past the links in your browser if you want to view the above links. I do not know how to paste links in the blog

  • Vote: I like it
  • 0
  • Vote: I do not like it

Comments Comments (3)
| Write comment?
»
3 years ago, # |
  Vote: I like it +3 Vote: I do not like it

No, it is not correct. In the second step, if you found a better solution to an already visited vertex $$$u$$$, you don't update all the nodes whose calculated distance was based on $$$u$$$. And if you did, the algorithm would surely take quadratic time.

I'm not going to copy-paste "Have you tried the following..." but I think if you had stress-tested and found a countertest, you would have understood why this algorithm doesn't work yourself.

→ Reply
  • »
    »
    3 years ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    Thanks Sir, for your reply...now I understand it. The only way of stress testing I know of is taking random inputs using random number generator. Are you speaking of that?

    → Reply