I want to find unreachable source-sink-Pairs and get an algorithm with time complexity of O(mn).
And my idea is it to solve it with BFS, because DFS could get stuck in a loop.
Input: G = (V, E), S in V, T in V
> Queue Q;
>
> Reach[][] = bool[|S|][|T|];
>
> For w in (s, w) in E:
> if w in T:
> Reach[s][w] = 1;
> Q.enqueue(w);
> w.sources.add(s);
>
>
> While Q != empty:
> v = Q.dequeue();
> forall w in (v, w) in E:
> w.sources.add(v.sources);
Q.enqueue(w);
> if w in T:
forall s in v.sources:
> Reach[s][w] = 1;
>
> print(not(Reach));
Is this algorithm correct?
Now I know that the time complexity of BFS is O(|V| + |E|).
Now let m be |S| and n be |T|. Then we time complexity would be O(|V| + |E| + mn), right? Because not(Reach) would have to iterate over m*n combinations?
And how could I proof the correctness of this algorithm?
Thanks for any help. Maybe someone knows a good resource for this kind of problems that I could read. Probably graph theory books.
I tried to realize the BFS algorithm and I tried to read about the theory behind BFS.
Btw. is there no way to embed LaTeX in blockcodes?