JOIN
 Select a Forum     Round Tables New Member Discussions News Discussions Algorithm Matches Marathon Matches NASA Tournament Lab TopCoder Cookbook High School Matches Sponsor Discussions Development Forums Design Forums Search | Watch Thread  |  My Post History  |  My Watches  |  User Settings View: Flat (newest first)  | Threaded  | Tree Previous Thread  |  Next Thread Forums Tutorial Discussions Introduction to graphs and their data structures Is this a shortest path problem or not?
 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=graphsDataStrucs2and 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.
 Forums Tutorial Discussions Introduction to graphs and their data structures Is this a shortest path problem or not? Previous Thread  |  Next Thread