I have a finite directed graph (of several weakly connected components).
Having two elements I need to check if there is a path from the first one to the second one.
The easiest solution is to create the incidence matrix and then using it calculate the connectivity matrix (the further is obvious). But I feel it is not the most efficient way in terms of startup time and memory space.
What is a more efficient way (taking into account that there are several components between which there are no links)?
Moreover the following may be used for optimization: In each connected component K, existence of a path needs to be checked only from a fixed vertex B(K) to other elements of K only. And it is expected to never check if there is a path (we know that there is none by definition of connected components, however) from an element of one connected component to an element of another connected component.
I write in Ada.
