In pathfinding, what is the difference between DFS and Dijkstra?

Question

I'm studying about DFS and Dijkstra. In my simple test cases, most of them shows that DFS is faster. Passing every nodes costs the same in my test cases. But most people prefer Dijkstra to DFS in pathfinding because Dijkstra is so accurate.

So, what's the difference between DFS and Dijkstra? Also, what are the pros and cons of each algorithm?

Hemorrhoidectomy

I would disagree @Dukeling – Markowitz

@Fubar With which part, and why... – Ergotism

Answer 1

DFS keeps jumping along nodes until it finds a path, While Dijkstra is more similar to a BFS except it keeps track of weights (not all paths have equal cost) and will keep checking the shortest path not already checked until it gets to the target.

In general DFS is (usually) the fastest way to find a path and can be implemented very easily with recursion, but Dijkstra's algorithm is the fastest general way to find the shortest possible path.

In a less general case there is A*, which is Dijkstra's algorithm with some extra heuristics on top to guess which paths might be better to check first. This will also find the shortest possible path, but may do so faster if your heuristic is good.

EDIT:

I should add, that if you want a "pretty good" path in a hurry and heuristics are available, that DFS with heuristics can often be a good choice if your graph doesn't have too many dead ends. This is called Greedy Best First Search and is a good, underutilized path finding algorithm for use in e.g. games, where you can design your maps to have few dead ends, or road maps where A* is prohibitively expensive.

Swordfish

Answer 2

Most of them shows that DFS is faster

DFS is faster as there is less overhead. DFS use stack, pop-ing and add-ing to stack is fast. Whereas, the most efficient Dijkstra implemented with heap, adding to heap is slower. Running time of DFS is O(V + E), Dijkstra is O((V + E) log V). Noticed Dijkstra has log V added, it is the cost of adding to the heap, hence it is slower than DFS.

Most people prefer Dijkstra to DFS in pathfinding because Dijkstra is so accurate.

Well, Dijkstra finds the shortest path from the starting point.

DFS does not guarantee shortest path, it would just generate a path that visits very nodes in the graph.

BFS also finds the shortest path

Dijkstra finds the shortest path for weighted graphs. If the graph does not have weighted edges, then BFS or Dijkstra would be fine.

Settee

> visits very nodes in the graph < very what? – Overfill