made easy

Question

can anyone explain how dijkstras will behave as BFS whwn a graph is unweighted?

 

Comments

If the graph is un weighted why the hell we need shortest path algorithm? we can use any traversal

is DFS can be USED to find shortest path between any two vertices?

---

DFS can be used for traversal.

Since they asked which algorithm will work same as Dijksras I thought it is DFS. I dont know the answer, some random guess.

I thought of knowing how dijkstras will behave as BFS ..

---

DFS can be used for traversal.

ok, but i am asking is DFS can be used as " finding shortest path between two vertices if graph is unweighted and connected "

Should be NO...

let K$_3$ is a complete undirected graph, then by applying DFS, you got as

1-->2 -->3, this indicates shortest path between 1 and 3 is 2 edge long, but it is not true !

if you apply BFS, then it will say, 1-->2 and 1-->3 ==> correct !

 

Coming to Prims(krushkal), if all edges are equal weight (i.e., indirectly it is saying unweighted), they may result more than one Spanning tree, So we can't guarantee that " it will result shortest path between any vertices at any time. "

Answer 1

In an unweighted graph,priority queue will behave like a simple queue (as all the connected edges is represented as 1) with FIFO policy.At first, the first frontier will be pushed into the queue & explored(nodes which are just a single edge away from the source node) and then the second frontier,and so on.This behavior resembles that of BFS.

Answer 2

For unweighted graph we can find single pair shortest path using BFS . IT will take O(n+m) .