# A new simple algorithm for the two paths problem

{pause}
Algorithm principle:

{carousel #algo-deux-chemins}
----
> ![](dessins/preuve-deux-chemins-graphe.svg)
---
> ![](dessins/preuve-deux-chemins-P.svg)
---
> ![](dessins/preuve-deux-chemins-cross.svg)
---
> ![](dessins/preuve-deux-chemins-separation-instances.svg)
---
> ![](dessins/algo-deux-chemins-solution-trous.svg)
---
> ![](dessins/algo-deux-chemins-solution.svg)

{change-page="algo-deux-chemins"}

{change-page="algo-deux-chemins"}

{change-page="algo-deux-chemins"}

{change-page="algo-deux-chemins"}

{change-page="algo-deux-chemins"}

{pause #algorithme}
Final algorithm:
![](dessins/algo-final-1.png){width=434 height=185}
![](dessins/algo-final-2.png){width=434 height=185}

{pause up="algorithme"}
**Caracteristics:**

{pause}
- **$O(nm)$ complexity.**

{pause}
- **The only external calls are to simple search algorithms.**

{pause}
- **Each procedure takes $\sim 10$ lines of pseudo-code.**

{pause}
$\rightarrow$ easy to implement algorithm with a reasonable complexity.

{pause}
With balanced instances (e.g. random searches on random graphs) we expect a complexity of $O(m\log n)$ or $O(n\log m)$.