How does Depth First-Search visit a node?

Question

An algorithm may come upon a node a second time, i.e. there might be two paths to the node. The algorithm needs to know which path was shorter.

When the Best First Search reaches a node that it has visited before, it is possible that the previous visit had a longer path. When this happens, the open and closed lists need updating. This can not happen with an A* search.

Question: Can this happen with a DFS?

The answer is yes, but I thought it was no. Why is it yes? I thought that once a node has been visited it wont go back to it.

Answer 1

If you have a graph like this

A
|\
B \
|  E
C /
|/
D

and traverse it depth-first, from left to right, the following pathes will be visited in that order:

A
AB
ABC
ABCD
AE
AED

You see, the first visit of D is on a longer path (ABCD) than the second one (AED).

Answer 2

DFS strategy will visit a node as many times as it finds a path to it. It wouldn't continue visiting from that node down, but it would register the visit itself. This is essential for DFS edge classification.

For example, consider running DFS on this graph:

When you reach node C for the first time, the path is A-B-C. When you reach C for the second time, the path is A-C, which is shorter.