BFS to find out the shortest path between two given vertices [Solved]

Revision en2, by The_mysterio, 2020-12-27 21:07:03

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

History

 
 
 
 
Revisions
 
 
  Rev. Lang. By When Δ Comment
en2 English The_mysterio 2020-12-27 21:07:03 9
en1 English The_mysterio 2020-12-27 20:42:44 1521 Initial revision (published)