Editing Iterative deepening depth-first search (section)

=== Bidirectional IDDFS ===
IDDFS has a bidirectional counterpart,<ref name="re1985"/>{{rp|6}} which alternates two searches: one starting from the source node and moving along the directed arcs, and another one starting from the target node and proceeding along the directed arcs in opposite direction (from the arc's head node to the arc's tail node). The search process first checks that the source node and the target node are same, and if so, returns the trivial path consisting of a single source/target node. Otherwise, the forward search process expands the child nodes of the source node (set <math>A</math>), the backward search process expands the parent nodes of the target node (set <math>B</math>), and it is checked whether <math>A</math> and <math>B</math> intersect. If so, a shortest path is found. Otherwise, the search depth is incremented and the same computation takes place.

One limitation of the algorithm is that the shortest path consisting of an odd number of arcs will not be detected. Suppose we have a shortest path <math>\langle s, u, v, t \rangle.</math> When the depth will reach two hops along the arcs, the forward search will proceed from <math>u</math> to <math>v</math>, and the backward search will proceed from <math>v</math> to <math>u</math>. Pictorially, the search frontiers will go through each other, and instead a suboptimal path consisting of an even number of arcs will be returned. This is illustrated in the below diagrams:

[[File:Bidirectional iterative deepening depth-first search search frontier pass through each other.png|thumb|Bidirectional IDDFS|400px]]

What comes to space complexity, the algorithm colors the deepest nodes in the forward search process in order to detect existence of the middle node where the two search processes meet.

Additional difficulty of applying bidirectional IDDFS is that if the source and the target nodes are in different strongly connected components, say, <math>s \in S, t \in T</math>, if there is no arc leaving <math>S</math> and entering <math>T</math>, the search will never terminate.

==== Time and space complexities ====

The running time of bidirectional IDDFS is given by

{{center|
: <math>2\sum_{k = 0}^{n / 2} b^k</math>
}}

and the space complexity is given by

{{center|
: <math>b^{n/2},</math>
}}

where <math>n</math> is the number of nodes in the shortest <math>s,t</math>-path. Since the running time complexity of iterative deepening depth-first search is <math>\sum_{k=0}^n b^k</math>, the speedup is roughly

{{center|
: <math>\frac{\sum_{k=0}^n b^k}{2\sum_{k=0}^{n/2} b^k} =\frac{\frac{1 - b^{n+1}}{1-b}}{2\frac{1 - b^{n/2 + 1}}{1-b}} = \frac{1-b^{n+1}}{2(1 - b^{n/2 + 1})} = \frac{b^{n+1} - 1}{2(b^{n/2+1} - 1)} \approx \frac{b^{n+1}}{2b^{n/2+1}} = \Theta(b^{n/2}).</math>
}}

==== Pseudocode ====

 '''function''' Build-Path(s, &mu;, B) '''is'''
     &pi; &larr; Find-Shortest-Path(s, &mu;) ''(Recursively compute the path to the relay node)''
     remove the last node from &pi;
     '''return''' &pi; <math>\circ</math> B ''(Append the backward search stack)''

 '''function''' Depth-Limited-Search-Forward(u, &Delta;, F) '''is'''
     '''if''' &Delta; = 0 '''then'''
         F &larr; F <math>\cup</math> {u} ''(Mark the node)''
         '''return'''
     '''foreach''' child '''of''' u '''do'''
         Depth-Limited-Search-Forward(child, &Delta; − 1, F)

 '''function''' Depth-Limited-Search-Backward(u, &Delta;, B, F) '''is'''
     prepend u to B
     '''if''' &Delta; = 0 '''then'''
         '''if''' u '''in''' F  '''then'''
             '''return''' u ''(Reached the marked node, use it as a relay node)''
         remove the head node of B
         '''return null'''
     '''foreach''' parent '''of''' u '''do'''
         &mu; &larr; Depth-Limited-Search-Backward(parent, &Delta; − 1, B, F)
         '''if''' &mu; <math>\neq</math> '''null''' '''then'''
             '''return''' &mu;
     remove the head node of B
     '''return null'''

 '''function''' Find-Shortest-Path(s, t) '''is'''
    '''if''' s = t '''then'''
        '''return''' &lt;s&gt;
    F, B, &Delta; &larr; &empty;, &empty;, 0
    '''forever do'''
        Depth-Limited-Search-Forward(s, &Delta;, F)
        '''foreach''' &delta; = &Delta;, &Delta; + 1 '''do'''
            &mu; &larr; Depth-Limited-Search-Backward(t, &delta;, B, F)
            '''if''' &mu; <math>\neq</math> '''null then'''
                '''return''' Build-Path(s, &mu;, B) ''(Found a relay node)''
        F, &Delta; &larr; &empty;, &Delta; + 1