Liveramp six-degree 问题

一会 准备做liveramp的online interview，
话说听说的六度问题（six-degree kevin bacon）哪位大大做过呢。。。

我自己怎么感觉很像all-pairs-shortest-paths O(|V|^3)的复杂度

为什么网上都是双向BFS什么的，那时间复杂度是O(b^(d/2))。。。怎么比较呢。、。算是多项式级的么