Algorithm: Iterative Deepening Depth First Search(IDDFS) not optimal

I probably understood the IDDFS algorhithm incorrectly.

I understand the algorhitm as:
Step 1)Do DFS, until you reach max depth (In my case it goes right to left)
Step 2)Mark every Node you pass as visited.
Step 3)Once you explore the graph fully increase depth by 1 and repeat process.

Here is a problem i came up with. (image with graph)

I ordered the nodes being processed in each depth.

In depth 3, it goes to node 9 from node 5 first ,even when in last depth it went from node 3. -> node 9 gets set as visited and can not be accesed by node 3 and thus way not finding the optimal way.

One way around it is to ignore loops and just dont add anything as visited, but that is not viable strategy for bigger graphs.

Thanks for your problem solving skills

https://stackoverflow.com/questions/67326941/algorithm-iterative-deepening-depth-first-searchiddfs-not-optimal April 30, 2021 at 09:08AM