# A Pathfinding Problem for Fork-Join Directed Acyclic Graphs with Unknown Edge Length
## 5 A Solution to PFJUEL  
In this section, we present a solution method to PFJUEL that gives a canonical estimate for FJ-DAGs. It is a strategy defined as follows Algorithm 1:  
```
1:While all goal paths have at least one unsaturated edge:
2: Let \(S\) be the set of such an unsaturated edge \(e\) that
3: (i) \(e\) is on a goal path with the shortest estimated length, and
4: (ii) \(e\) is not in any sub FJ-DAG for which the current
5: \(\text{estimate is terminal}\);
6: If \(|S|>1\), then let \(S^{\prime}\) be the set of edges in \(S\)
7: \(\text{having the estimated length minimum in }S\);
8: else\(S^{\prime}:=S\);
9: If \(|S^{\prime}|>1\), then let \(S^{\prime\prime}\) be the set of edges in \(S^{\prime}\)
10: \(\text{having the level highest in }S^{\prime}\);
11: else\(S^{\prime\prime}:=S^{\prime}\);
12: \(\text{Choose one edge from }S^{\prime\prime}\) and issue an oracle call to it;
13:endwhile. ```  
**Algorithm 1**Shortest Path Increment from Outmost Edges (SPIOE):  
**Remark 1**. : _At line 12, there may be more than one edge in \(S^{\prime\prime}\). To make the strategy deterministic, we need some rule to select one edge; e.g., introducing a total order to the set of edges._  
Let \(h^{*}\) be the length of a shortest goal path. Suppose that an edge \((v_{i},v_{j})\) is selected in the while loop, and \((v_{i},v_{j})\) is on a goal path \(\pi\) whose estimated length already reaches \(h^{*}\). If \(\hat{w}(v_{(i)},v_{(i+1)})<w(v_{(i)},v_{(i+1)})\), then \(search_{c}(v_{(i)},v_{(i+1)})\) returns \"no\" and the estimated length of \(\pi\) becomes \(h^{*}+1\). Such an oracle call is unnecessary for satisfying the requirement R2. We call such a fail call a waste fail call. Waste fail calls are unavoidable if the length of each edge is initially unknown. **Lemma 4**. : _If waste fail calls do not occur, then the estimate given by SPIOE is canonical._  
Proof. : If the oracle call is not a success call, then SPIOE increments the length of a goal path with the shortest estimated length by one. Since waste fail calls do not occur, the estimated length of every goal path does not exceed the length of the shortest goal path, and therefore SPIOE gives a homogeneous estimate when it terminates. We show that the violation of C2-C4 does not occur in any sub FJ-DAG during the execution of SPIOE. This is proved by mathematical induction in the number of iterations. Initially, the estimate is canonical. Assume that the current estimate satisfies C2-C4 in any sub FJ-DAG. Suppose that the estimated length of the upper edge \(e_{i}^{t}\) of a sub FJ-DAG \(G_{i}\) has been updated; i.e., incremented by one. We first show that C2-C4 still hold in \(G_{i}\) after the update. C2: If \(e_{i}^{b}\) is saturated just before the update, then a violation of C2 does not occur. Suppose that \(e_{i}^{b}\) is unsaturated just before the update. Note that every goal path that contains \(e_{i}^{t}\) also contains \(e_{i}^{b}\). Then, by line 7, \(\hat{w}(e_{i}^{t})\leq\hat{w}(e_{i}^{b})\) holds just before the update. Therefore, C2 is still true after the update. C3: Since \(\hat{w}(e_{i}^{t})\geq\hat{w}(G_{i})^{\dagger}\) holds just before the update, then C3 is still true after the update. C4: If \(\hat{w}(e_{i}^{t})<\hat{w}(G_{i})^{\downarrow}+1\) just before the update, then C4 is still true after the update. Suppose that \(\hat{w}(e_{i}^{t})=\hat{w}(G_{i})^{\downarrow}+1\) just before the update. Any goal path that contains \(e_{i}^{t}\) also contains an edge in a minimum unsaturated cut of \(G_{i}\). Then, the path contains an unsaturated edge with an estimated length no greater than \(\hat{w}(G_{i})^{\downarrow}\). By line 7, SPIOE does not choose \(e_{i}^{t}\) because \(\hat{w}(e_{i}^{t})\) is not minimum in unsaturated edges on the path. The case that \(e_{i}^{b}\) has been updated is similar. Next, we show that C2-C4 are still true in other sub FJ-DAGs after the update. Since C2 is the condition for the top and the bottom edge of each sub FJ-DAG, C2 is still true in any sub FJ-DAG after the update.