Bohm criterion for complex plasmas which are composed of electrons, negative and positive ions as well as dust grains is investigated with Sagdeev potential, taking into account the self-consistent dust charge variation. The numerical solutions show that the positive ion and dust Bohm velocities increase with the growth of the dust density, while both of them decrease with the growth of negative ion density. Furthermore, the interactions between the two Bohm velocities exist. The results are examined to be reliable by the quantitative analysis of Sagdeev potential. (c) 2005 Elsevier B.V. All rights reserved.