Redian新闻
>
A家电面被拒贡献个题攒人品吧
avatar
A家电面被拒贡献个题攒人品吧# JobHunting - 待字闺中
h*a
1
给一个无向图找出给定起始点到给定结束点的所有最短路径并打印
avatar
w*x
2
dijkstra只是找一条路径打印,就算是现场实现这个打印一条最短路径算法的代码也是
不简单的,A家啥时候这么难了
avatar
H*r
3
啥叫”所有最短路径“?

【在 h****a 的大作中提到】
: 给一个无向图找出给定起始点到给定结束点的所有最短路径并打印
avatar
A*u
4
靠。。。竟然搞这种

【在 h****a 的大作中提到】
: 给一个无向图找出给定起始点到给定结束点的所有最短路径并打印
avatar
f*y
5
the shortest part may not be unique

【在 H****r 的大作中提到】
: 啥叫”所有最短路径“?
avatar
d*x
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 的大作中提到】
: 给一个无向图找出给定起始点到给定结束点的所有最短路径并打印
avatar
d*x
7
这个真心不难
O(n^3)的all pair最短路径一共不过5行,加上上面这个dfs打印最短路径的程序也就10
分钟
也许这故事说明算法导论还是要读读的,光靠背面试题吧。。

【在 w****x 的大作中提到】
: dijkstra只是找一条路径打印,就算是现场实现这个打印一条最短路径算法的代码也是
: 不简单的,A家啥时候这么难了

avatar
C*U
8
clrs里面的一章吧。。。

【在 h****a 的大作中提到】
: 给一个无向图找出给定起始点到给定结束点的所有最短路径并打印
avatar
o*n
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
: 分钟
: 也许这故事说明算法导论还是要读读的,光靠背面试题吧。。

avatar
H*r
10
devilphoenix 太牛

10

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

avatar
H*r
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
: 也是

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

【在 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
: 也是

avatar
w*x
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

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

离之

【在 w****x 的大作中提到】
:
: 好像不能假定任何两点之间的距离都知道吧,没直接连上怎么办?
: 没记录遍历过的点。程序有跑过吗?

avatar
H*r
15
对啊,这graph是咋表示的?要是点对点矩阵的话任意两点间距离还是有的, 不相连的
话是Infinity...

【在 w****x 的大作中提到】
:
: 好像不能假定任何两点之间的距离都知道吧,没直接连上怎么办?
: 没记录遍历过的点。程序有跑过吗?

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

and make

【在 H****r 的大作中提到】
: 对啊,这graph是咋表示的?要是点对点矩阵的话任意两点间距离还是有的, 不相连的
: 话是Infinity...

avatar
h*t
17
这个用 BFS 遍历图不就可以吗?

【在 h****a 的大作中提到】
: 给一个无向图找出给定起始点到给定结束点的所有最短路径并打印
avatar
d*x
18
仔细想想。。?

【在 h****t 的大作中提到】
: 这个用 BFS 遍历图不就可以吗?
avatar
h*t
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 的大作中提到】
: 仔细想想。。?
相关阅读
logo
联系我们隐私协议©2024 redian.news
Redian新闻
Redian.news刊载任何文章,不代表同意其说法或描述,仅为提供更多信息,也不构成任何建议。文章信息的合法性及真实性由其作者负责,与Redian.news及其运营公司无关。欢迎投稿,如发现稿件侵权,或作者不愿在本网发表文章,请版权拥有者通知本网处理。