We use cookies to ensure you have the best browsing experience on our website. Please read our cookie policy for more information about how we use cookies.
The difference between the BFS(breadth-first search) and Dijstra-shortest path algorithm is the relaxation.
The pawn-move distance is monotonic function and hence it is suitable to use BFS. But the queen-move distance is non-monotonic function when a node is just explored, thus it requires relaxation . Dijkstra's shortest path algorithm is more suitable in this case. In our case we are doing rook move, for which Dijkstra is suitable as well.
The BFS ends when we explore the goal node. The Dijkstra's shortest path algorithm ends when we pop() goal node from the queue.
Finally I did it with bidirectional-Dijkstra . I am not sure if it is faster than normal Dijkstra though. I guess in cases bidirectional-Dijkstra algorithm may expand more nodes than normal Dijkstra algorithm.
Cookie support is required to access HackerRank
Seems like cookies are disabled on this browser, please enable them to open this website
Castle on the Grid
You are viewing a single comment's thread. Return to all comments →
The difference between the
BFS
(breadth-first search) andDijstra-shortest path
algorithm is the relaxation.The pawn-move distance is monotonic function and hence it is suitable to use BFS. But the queen-move distance is non-monotonic function when a node is just explored, thus it requires relaxation . Dijkstra's shortest path algorithm is more suitable in this case. In our case we are doing rook move, for which Dijkstra is suitable as well.
The BFS ends when we explore the goal node. The Dijkstra's shortest path algorithm ends when we
pop()
goal node from the queue.Finally I did it with bidirectional-Dijkstra . I am not sure if it is faster than normal Dijkstra though. I guess in cases bidirectional-Dijkstra algorithm may expand more nodes than normal Dijkstra algorithm.