JOIN
Get Time
forums   
Search | Watch Thread  |  My Post History  |  My Watches  |  User Settings
View: Flat (newest first)  | Threaded  | Tree
Previous Thread  |  Next Thread
Is this a shortest path problem or not? | Reply
I was reading the tutorial written on Graph Search here:

http://www.topcoder.com/tc?module=Static&d1=tutorials&d2=graphsDataStrucs2

and I saw that at the end of page 2, the author suggests practicing on problem "Inviational 02 Semifinal Room 2 - Div 1 500 - Escape " to understand how BFS works. However, it occurs to me that this is a shortest problem and we need a priority queue and Dijkstra's algorithm to solve this.

Somewhere in the tutorial, the author mentions:

"BFS has the extremely useful property that if all of the edges in a graph are unweighted (or the same weight) then the first time a node is visited is the shortest path to that node from the source node."

But in the problem above, we have different costs as the edge weights so I got confused here.

Can we solve this problem by applying pure BFS and a regular queue?
Re: Is this a shortest path problem or not? (response to post by dolaposman) | Reply
Since every edge has cost 1 (if it points to a harmful square) or 0 (if it points to a normal square), you can use the regular BFS algorithm with a deque: Push a vertex to the front of the deque in case of distance 0, and a vertex to the back of the deque in case of distance 1. That way, the distance order invariant of the BFS is preserved in the deque, and everything works.
RSS