The Gateway to Computer Science Excellence
0 votes
85 views
can anyone explain how dijkstras will behave as BFS whwn a graph is unweighted?

 

in Algorithms by (481 points) | 85 views
0
maybe I'm wrong but is this even logical? :p
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
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 ..
+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. "

2 Answers

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.
by Junior (909 points)
0 votes

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

by Boss (36.7k points)

Related questions

Quick search syntax
tags tag:apple
author user:martin
title title:apple
content content:apple
exclude -tag:apple
force match +apple
views views:100
score score:10
answers answers:2
is accepted isaccepted:true
is closed isclosed:true
50,737 questions
57,381 answers
198,528 comments
105,321 users