IHB Posted March 28, 2017 Share Posted March 28, 2017 (edited) I'm writing my school project and the last thing I neef is a depth first search of a graph containing nodes, trying to find the shortest path from A to B. Is it possible with a depth first search? Or should I use a breadth first? any help appreciated Edited March 28, 2017 by IHB Quote Link to comment Share on other sites More sharing options...
Gosre Posted March 28, 2017 Share Posted March 28, 2017 (edited) It's easily possible with both; just depends what kind of running time you want out of it. Suggestion: Do both so that you understand the differences between the two. Edited March 28, 2017 by Gosre Quote Link to comment Share on other sites More sharing options...
layman Posted March 28, 2017 Share Posted March 28, 2017 (edited) Assuming you are talking about unweighted undirected graphs, DFS cannot be used to find the shortest path in a graph. Only BFS is capable of that. Edited March 28, 2017 by layman Quote Link to comment Share on other sites More sharing options...
IHB Posted March 28, 2017 Author Share Posted March 28, 2017 4 hours ago, Gosre said: It's easily possible with both; just depends what kind of running time you want out of it. Suggestion: Do both so that you understand the differences between the two. 3 hours ago, layman said: Assuming you are talking about unweighted undirected graphs, DFS cannot be used to find the shortest path in a graph. Only BFS is capable of that. It will be undirected and weighted, should I be using Dijkstra's algorithm? Does Dijkstra's work for directed graphs aswell? Quote Link to comment Share on other sites More sharing options...
Explv Posted March 28, 2017 Share Posted March 28, 2017 22 minutes ago, IHB said: It will be undirected and weighted, should I be using Dijkstra's algorithm? Does Dijkstra's work for directed graphs aswell? There are tonnes of algorithms you can use... Just do some research on Google. Quote Link to comment Share on other sites More sharing options...
LoudPacks Posted March 28, 2017 Share Posted March 28, 2017 A* is better than Djikstra imo because it doesn't need to traverse the whole tree. Quote Link to comment Share on other sites More sharing options...
