Shortest path for unweighted graph using iterative depth first search algorithm

Question

I have managed to find shortest path for unweighted graph using recursive dfs. Here is such an attempt.

void dfsHelper(graph*& g, int start,int end, bool*& visited, int& min, int i) {
    visited[start] = true;
    i = i + 1;
    if (start == end) {
        if (i<=min) { min = i; }
    }
    node* current = g->adj[start];
    while (current != NULL) {
        if (!visited[current->dest]) {
            dfsHelper(g, current->dest,end, visited,min,i);
        }
        current = current->next;
    }
    visited[start] = false;
}

However for an iterative algorithm of dfs such as this one, how should I approach.

void dfsItr(graph*& g, int start, int end) {
    bool* isVisited = new bool[g->numVertex];
    for (int i = 0; i < g->numVertex; ++i) {
        isVisited[i] = false;
    }
    stack<int> st;
    isVisited[start] = true;
    st.push(start);

    while (!st.empty()) {
        start = st.top();
        cout << start << " ";
        st.pop();
        node* current = g->adj[start];
        while (current != NULL) {
            if (!isVisited[current->dest]) {
                isVisited[current->dest] = true;
                st.push(current->dest);
                if (current->dest == end) {
                    cout << current->dest << endl; 
                }
            }
            current = current->next;
        }

    }
}

Is there any algorithm detailing about the procedure to follow. I am well aware of finding shortest path using BFS algorithm as given here or as suggested here. My initial intuition as to why such idea would work for BFS is that the traversal happens layer by layer,multiple children share same parent in each layer, so it is easy to backtrack just by following the parent node. In iterative dfs, it is not the case. Can someone shed some light as to how to proceed. Is there any proven algorithm to tackle this scenario. Thanks.

You might have found _one_ shortest path with the first algorithm by luck, but it's not correct in general. The only way you could reasonably use DFS is with iterative deepening and that would be far less efficient than BFS. BFS is the natural approach. — Gene, Dec 03 '19 at 04:39
May this help https://stackoverflow.com/questions/22715791/depth-first-search-to-find-shortest-path — DRV, Dec 03 '19 at 08:54
Please post sample input and output too, it can be helpful for testing! And, also structure of `graph`. — kiner_shah, Dec 07 '19 at 04:45

score 0 · Answer 1 · answered Dec 10 '19 at 01:52

It is not entirely clear for me what you are asking about...

If you ask about how to optimise iterative implementation of DFS, the one thing I'd do here is not use stack but write own collection that has LIFO interface but does pre-allocation of memory.
Other room for optimisation is not to use stream operators since they are significantly slower than printf. Check out this answer section about performance. Also, does it really make sense to print to STDOUT all the time? If performance is the key this might be done once every couple of iterations, since IO operations are really slow.

If you're asking about what algorithm is better than DFS approach it is hard to answer since it always depends on given problem. If you want to find best path between nodes, go for BFS-based (e.g. Dijkstra algorithm) since it would perform best in unweighted graphs in comparison to DFS (btw. A* won't do the trick here, since with no weights and no fancy heuristic it'll just collapse to DFS). If you are more interested in this topic, you can find more info on what tricks you could do to optimise path-finding in this books series.

Last but not least, give some heuristics a try too. Maybe there's no need to do exhaustive search to find solution to your problem.

Tobias Hagge · Answer 2 · 2019-12-10T05:53:48.000

Here is an example that illustrates why depth-first search, even with some optimizations, can be a bad idea. (It's almost always a bad idea, but the illustration does not go that far).

Suppose your graph is the complete graph on nodes 0, ..., n, that is, the graph containing every possible edge. Suppose further that the edges always appear in order in the data structure, and you want to find the shortest path from 0 to n.

Naive depth-first search will explore (n-1)! paths before it finds the optimal path. Breadth-first search explores n paths. Both cases are essentially worst cases (edit: worst-case orderings for this graph) for their respective algorithms.

You could optimize depth-first search in a couple of ways:

1) Prune the search if the current path is one hop shorter than the best successful path so far, and is not a successful path.

2) More aggressively, each time you visit a node for the first time, store the length of the current path in the node. Each later time you visit, compare the length of the current path with the previously stored length. If the new path is shorter, store the new length. Otherwise, prune the search.

Of these two, (2) is the more aggressive optimization. It's entirely worse than breadth-first search. In breadth-first search, every time you pass through a node it is because you reached it by a shortest path, and at that point the node becomes a dead end for all further path traversals. Neither of these things are the case for depth-first search. Additionally, the (asymptotic) memory cost of storing the lengths is no better than that of using a breadth-first queue.

Shortest path for unweighted graph using iterative depth first search algorithm

2 Answers2