A家电面被拒贡献个题攒人品吧 - 未名空间MITBBS历史存档

国际科技财经博客移民网络热点娱乐民生时事公众号

Redian新闻

>未名空间

>JobHunting - 待字闺中

A家电面被拒贡献个题攒人品吧

A家电面被拒贡献个题攒人品吧# JobHunting - 待字闺中

h*a2012-07-16 07:07

1 楼

给一个无向图找出给定起始点到给定结束点的所有最短路径并打印

w*x2012-07-16 07:07

2 楼

dijkstra只是找一条路径打印，就算是现场实现这个打印一条最短路径算法的代码也是
不简单的，A家啥时候这么难了

H*r2012-07-16 07:07

3 楼

啥叫”所有最短路径“？

【在 h****a 的大作中提到】

: 给一个无向图找出给定起始点到给定结束点的所有最短路径并打印

A*u2012-07-16 07:07

4 楼

靠。。。竟然搞这种

【在 h****a 的大作中提到】

: 给一个无向图找出给定起始点到给定结束点的所有最短路径并打印

f*y2012-07-16 07:07

5 楼

the shortest part may not be unique

【在 H****r 的大作中提到】

: 啥叫”所有最短路径“？

d*x2012-07-16 07:07

6 楼

一个简洁一点的办法
先用O(V^3)的算法找出all pair shortest paths
设起点为S，终点为T
然后从目标点递归回溯，回溯过程中取点v，使得S到v距离加上v到其下一点u的距离之
和为S到u的距离。大体上如下：
find_path(Vertex source, Vertex target)
static list path
path.push(target)
if source == target
output path
path.pop(source)
return
for Vertex v in t.neighbors
if dist(source, v) + dist(v, target) == dist(source, target)
find_path(source, v)
path.pop(target)

【在 h****a 的大作中提到】

: 给一个无向图找出给定起始点到给定结束点的所有最短路径并打印

d*x2012-07-16 07:07

7 楼

这个真心不难
O(n^3)的all pair最短路径一共不过5行，加上上面这个dfs打印最短路径的程序也就10
分钟
也许这故事说明算法导论还是要读读的，光靠背面试题吧。。

【在 w****x 的大作中提到】

: dijkstra只是找一条路径打印，就算是现场实现这个打印一条最短路径算法的代码也是
: 不简单的，A家啥时候这么难了

C*U2012-07-16 07:07

8 楼

clrs里面的一章吧。。。

【在 h****a 的大作中提到】

: 给一个无向图找出给定起始点到给定结束点的所有最短路径并打印

o*n2012-07-16 07:07

9 楼

You can get a much better algorithm than O(n^3) if you modify
Dijkstra's algorithm. Most likely your O(n^3) algorithm would
fail miserably.
ps: this question is pure BS for a phone interview.

10
也是

【在 d**********x 的大作中提到】

: 这个真心不难
: O(n^3)的all pair最短路径一共不过5行，加上上面这个dfs打印最短路径的程序也就10
: 分钟
: 也许这故事说明算法导论还是要读读的，光靠背面试题吧。。

H*r2012-07-16 07:07

10 楼

devilphoenix 太牛

10

【在 d**********x 的大作中提到】

H*r2012-07-16 07:07

11 楼

对哈，这个问题当电面题的确太过分袅...

【在 o****n 的大作中提到】

: You can get a much better algorithm than O(n^3) if you modify
: Dijkstra's algorithm. Most likely your O(n^3) algorithm would
: fail miserably.
: ps: this question is pure BS for a phone interview.
:
: 10
: 也是

d*x2012-07-16 07:07

12 楼

恩，Dijkstra是正着贪过去，标记每点的最短路径再回溯
我要defense两点，一前面有人说了Dijkstra不好写，二复杂度是由回溯部分限制的，
除非图很稀疏。

【在 o****n 的大作中提到】

w*x2012-07-16 07:07

13 楼

好像不能假定任何两点之间的距离都知道吧，没直接连上怎么办？
没记录遍历过的点。程序有跑过吗？

【在 d**********x 的大作中提到】

: 一个简洁一点的办法
: 先用O(V^3)的算法找出all pair shortest paths
: 设起点为S，终点为T
: 然后从目标点递归回溯，回溯过程中取点v，使得S到v距离加上v到其下一点u的距离之
: 和为S到u的距离。大体上如下：
: find_path(Vertex source, Vertex target)
: static list path
: path.push(target)
: if source == target
: output path

d*x2012-07-16 07:07

14 楼

任意两点的距离可以用Floyd-Marshall得到，O(n^3)
或者用Dijkstra求单源最短路径，O(n^2)。

离之

【在 w****x 的大作中提到】

:
: 好像不能假定任何两点之间的距离都知道吧，没直接连上怎么办？
: 没记录遍历过的点。程序有跑过吗？

H*r2012-07-16 07:07

15 楼

对啊，这graph是咋表示的？要是点对点矩阵的话任意两点间距离还是有的，不相连的
话是Infinity...

【在 w****x 的大作中提到】

:
: 好像不能假定任何两点之间的距离都知道吧，没直接连上怎么办？
: 没记录遍历过的点。程序有跑过吗？

d*x2012-07-16 07:07

16 楼

Floyd Marshall里面是先构建一矩阵，无穷标记为-1
然后逐个update，直到取到所有最短距离

and make

【在 H****r 的大作中提到】

: 对啊，这graph是咋表示的？要是点对点矩阵的话任意两点间距离还是有的，不相连的
: 话是Infinity...

h*t2012-07-16 07:07

17 楼

这个用 BFS 遍历图不就可以吗？

【在 h****a 的大作中提到】

: 给一个无向图找出给定起始点到给定结束点的所有最短路径并打印

d*x2012-07-16 07:07

18 楼

仔细想想。。？

【在 h****t 的大作中提到】

: 这个用 BFS 遍历图不就可以吗？

h*t2012-07-16 07:07

19 楼

为什么不行？
抽空写了下。BFS 实现的。不算那个PrintAllPath() 的话，是O(E).
void PrintAllPath(PGNODE end, hash_map> &parentsMap,
vector &path) {
path.push_back(end);
int size = parentsMap[end].size();
if (size == 0) {
for (int i=path.size()-1; i>=0; i--)
cout << path[i]->value << ' ';
cout << endl;
path.pop_back();
return;
}
for (int j=0; jPrintAllPath(parentsMap[end][j], parentsMap, path);
}
path.pop_back();
}
void FindAllPath(PGNODE start, PGNODE end) {
queue q;
hash_set visited;
hash_map> parentsMap;
hash_map distance;
vector parents;
PGNODE pCur;
int curDis = 1, curLevelNum;
if (!start || !end)
return;
visited.insert(start);
parents.clear();
parentsMap[start] = parents;
distance[start] = 0;
q.push(start);
curLevelNum = 1;
while (!q.empty()) {
pCur = q.front();
q.pop();
curLevelNum--;
if (pCur == end)
break;
for (int i=0; ichildren.size(); i++) {
if (visited.find(pCur->children[i]) == visited.end()) {
q.push(pCur->children[i]);
visited.insert(pCur->children[i]);
distance[pCur->children[i]] = curDis;
parents.clear();
parents.push_back(pCur);
parentsMap[pCur->children[i]] = parents;
} else {
if (distance[pCur->children[i]] == curDis) {
parentsMap[pCur->children[i]].push_back(pCur);
}
}
}
if (curLevelNum == 0) {
curDis++;
curLevelNum = q.size();
}
}
vector path;
PrintAllPath(end, parentsMap, path);
}

【在 d**********x 的大作中提到】

: 仔细想想。。？