m********g
发帖数: 9 | 1 During a phone interview, I was asked how to implement a BFS algorithm to
find the shortest distance path from node A to node B in a graph. I asked is
it Dijkstra, and he said no.
Isn't BFS a special case of Dijkstra when there is no weight?
Strange. |
r***r
发帖数: 153 | 2 结果一样，但是Dijkstra成本高很多阿
BFS is O(|E|+|V|)
Dijkstra 有很多的priority queue操作，
如果用简单的堆实现，需要 O(|V|^2)
用复杂的Fibonacci heap，（可以得到最优complexity，但没有很多实际意义）也是 O
( |E| + |V| log |V| )
is
【在 m********g 的大作中提到】
: During a phone interview, I was asked how to implement a BFS algorithm to
: find the shortest distance path from node A to node B in a graph. I asked is
: it Dijkstra, and he said no.
: Isn't BFS a special case of Dijkstra when there is no weight?
: Strange.
|
c*****t
发帖数: 1879 | 3 For BFS to work on shortest path, there are restrictions on the path
weight. Otherwise, case like
1.1 1.1 1.1 5
A---- D --- E ----- F - G
\10 /1
B-----------------
would be screwed up. In this case, one has to use Dijkstra.
O
【在 r***r 的大作中提到】
: 结果一样，但是Dijkstra成本高很多阿
: BFS is O(|E|+|V|)
: Dijkstra 有很多的priority queue操作，
: 如果用简单的堆实现，需要 O(|V|^2)
: 用复杂的Fibonacci heap，（可以得到最优complexity，但没有很多实际意义）也是 O
: ( |E| + |V| log |V| )
:
: is
|
b******n
发帖数: 592 | 4 Why?
Is BFS a full search?
【在 c*****t 的大作中提到】
: For BFS to work on shortest path, there are restrictions on the path
: weight. Otherwise, case like
: 1.1 1.1 1.1 5
: A---- D --- E ----- F - G
: \10 /1
: B-----------------
: would be screwed up. In this case, one has to use Dijkstra.
:
: O
|
c*****t
发帖数: 1879 | |
b******n
发帖数: 592 | 6 Didn't find bfs on the webpage. bfs and dfs terms have been used in speech
recognition, that's where I get my idea of it from. I checked the wiki,
seems bfs will return when target node is found. It is easy to modify the
behaviour in implementation though. So the search only ends when the costs
of other node in the queue are larger than the found target node.
Thanks for the page though/
【在 c*****t 的大作中提到】
: 见
: http://www.cs.mcgill.ca/~cs251/OldCourses/1997/topic29/
|
c*****t
发帖数: 1879 | 7 ... It talked about BFS on the very top of page. Also has 2 figures...
With BFS, one has to "walk" along the edges in uniform speed to prevent
a node from updated with newer, shorter path.
【在 b******n 的大作中提到】
: Didn't find bfs on the webpage. bfs and dfs terms have been used in speech
: recognition, that's where I get my idea of it from. I checked the wiki,
: seems bfs will return when target node is found. It is easy to modify the
: behaviour in implementation though. So the search only ends when the costs
: of other node in the queue are larger than the found target node.
: Thanks for the page though/
|
