Sign in to follow this  

Graph Searching: Dijkstra's == BFS??

This topic is 3475 days old which is more than the 365 day threshold we allow for new replies. Please post a new topic.

If you intended to correct an error in the post then please contact us.

Recommended Posts

So I'm currently implementing a graph. The thing is, i don't want the user of my graph to care about nodes and adjacency etc. I have a initialise function that gives the search space of the graph in the form of a 2D array of vectors. I then have a CalculateShortestPath that takes starting position(vector) and a goal and returns a queue of points. The problem is, because CalculateShortestPath has no idea where the positions are in the graph, it needs to search the graph to find them. So then i asked myself... why couldn't i store the middle point of the graph when initialising and just use Dijkstra's algorithm (which doesn't require a target node) to find the node for my starting and target positions (vectors). So i searched the web to find what other people did, and it turns out you can either do a Depth-First search or a Breadth-first search. I've looked in various places and it seems that the Breadth-first search does exactly the same thing as Dijkstra's; in that it searches the closet to the starting node and spreads out evenly (like this: http://theory.stanford.edu/~amitp/game-programming/a-star/dijkstra.png) with the only difference that it doesn't create the shortest path at the end. What do you think? Am I missing something here or do they just distinguish them because the BFS's aim isn't to find the shortest path?

Share this post


Link to post
Share on other sites
Breadth-first search minimizes the number of edges in the path from start to finish; Dijkstra's minimizes the total cost of the edges. Breadth-first search is basically just a special case of Dijkstra's that takes advantage of the fact that all edge weights are 1 to simplify the implementation.

Share this post


Link to post
Share on other sites
Sign in to follow this