shortest path

Question

1)In an unweighted undirect connected graph , the shortest path from node S to every other node can be computed with the most efficient algo in time complexity of ____________assuming graph ha n vertices and e edges

O(n²)

O(n logn)

O(n+e)

O(n³)

2) Bellman ford shortest path finds whther any negative weighted cycle is reachable from source - true or not

Comments

@rupendra

BFS only gives shortest path from source to destination na? Does it give shortest path from S to all other nodes

BUT bellman doesnt work incase of negative cycles right?

---

Yes! source to destination , where domain of destination nodes is 'every possible node'.

BFS provides us the # of minimum number of edges required to reach every possible node from source. we can suppose every edge weight will correspond to same weight 'w'. then in that case or when there is no weight allocated , the shortest path from source to every possible node will correspond to , min edge length. in BFS , we traverse graph , level by level , and in that scenario it can't happen that you are traversing some node 'x' (which is in level 5 suppose ) before a node 'y' (which is in level 4 or any level less than 5).

yes it doesn't work in case of -ve weight cycle but question is about whether it can detect -ve weight cycle or not. and it can. focus its algorithm , how it works.it first relaxes it's edges 'n-1' times , so in that manner we will have shortest path from source to every other node. and what does it do in nth iteration? here it take care about -ve weight cycle , as during last run if weight to edges further decrease even after relaxing edges , it will confirm , certainly there is -ve cycle in graph. if in last run , the result is same as n-1 th run , it would confirm that there is no -ve weight cycle or if one exist then that is not reachable.

---

tanku :)

 well explained