Complexity
In the general case probabilistic inference is NP-hard.
For polytrees (singly connected networks), where there is at most one path connecting two nodes, the evaluation is O(Nodes).
There are several algorithms with the most promising one based on message passing (exploits also parallelism) [Pearl].