IHB Posted March 28, 2017 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
Gosre Posted March 28, 2017 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
layman Posted March 28, 2017 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
IHB Posted March 28, 2017 Author 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?
Explv Posted March 28, 2017 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.
LoudPacks Posted March 28, 2017 Posted March 28, 2017 A* is better than Djikstra imo because it doesn't need to traverse the whole tree.
