Jump to content
  • Advertisement
Sign in to follow this  
Trandafira

Graph Searching: Dijkstra's == BFS??

This topic is 3630 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
Advertisement
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  

  • Advertisement
×

Important Information

By using GameDev.net, you agree to our community Guidelines, Terms of Use, and Privacy Policy.

Participate in the game development conversation and more when you create an account on GameDev.net!

Sign me up!