The Gateway to Computer Science Excellence

0 votes

0

Even I got same doubt ...

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

But they asked which algorithm produces same output as Djkstras..I dont understand what does it mean

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

But they asked which algorithm produces same output as Djkstras..I dont understand what does it mean

0

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?

0

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 ..

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 ..

+1

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. "

0 votes

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.

- All categories
- General Aptitude 1.9k
- Engineering Mathematics 7.5k
- Digital Logic 2.9k
- Programming and DS 4.9k
- Algorithms 4.4k
- Theory of Computation 6.2k
- Compiler Design 2.1k
- Databases 4.1k
- CO and Architecture 3.4k
- Computer Networks 4.2k
- Non GATE 1.4k
- Others 1.4k
- Admissions 595
- Exam Queries 573
- Tier 1 Placement Questions 23
- Job Queries 72
- Projects 18

50,737 questions

57,381 answers

198,528 comments

105,321 users