効率的かわからんけど、障害物の頂点から頂点へのルートだけ考慮すればいいんでない?
こんな感じで
http://www.dotup.org/uploda/www.dotup.org4187748.png