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, 20178 yr by IHB

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, 20178 yr by Gosre

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, 20178 yr by layman

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?

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.

A* is better than Djikstra imo because it doesn't need to traverse the whole tree.