w*x
2 楼
dijkstra只是找一条路径打印,就算是现场实现这个打印一条最短路径算法的代码也是
不简单的,A家啥时候这么难了
不简单的,A家啥时候这么难了
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 的大作中提到】
: 给一个无向图找出给定起始点到给定结束点的所有最短路径并打印
先用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 的大作中提到】
: 给一个无向图找出给定起始点到给定结束点的所有最短路径并打印
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
: 分钟
: 也许这故事说明算法导论还是要读读的,光靠背面试题吧。。
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
: 分钟
: 也许这故事说明算法导论还是要读读的,光靠背面试题吧。。
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
: 也是
我要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
: 也是
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
h*t
19 楼
为什么不行?
抽空写了下。BFS 实现的。不算那个PrintAllPath() 的话,是O(E).
void PrintAllPath(PGNODE end, hash_map
vector
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; j
}
path.pop_back();
}
void FindAllPath(PGNODE start, PGNODE end) {
queue
hash_set
hash_map
hash_map
vector
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; 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
PrintAllPath(end, parentsMap, path);
}
【在 d**********x 的大作中提到】
: 仔细想想。。?
相关阅读
google team match后,一周内没有消息Google interview求建议Uber's head of HR to join Twitter放c code求老师傅指教关于投行offer 问题烙印高层又被软银踢走了employment at will 是啥意思VIPshop(美国上市)湾区招聘 Computer Vision工程师[bssd]这样的公司还能呆吗?大家觉得NextEV有前途吗?值得去吗?说个叔知道的startupZillow这个公司怎么样?比微软如何呢?Senior Developer Analyst请问amazon这个会是technical phone interview吗?H1B 6年renew中, 请问拿receipt去renew驾照给延几年? (转载)Oracle Cloud 老年主任级别的包裹能有36-40万么?中部一个startup,薪水是不是太低?好几个recruiter找我,同个公司相似职位名称咋回事??求netflix内推工作时间很短的公司可以不列在简历上么?