h****a
发帖数: 7 | 1 给一个无向图找出给定起始点到给定结束点的所有最短路径并打印 |
w****x
发帖数: 2483 | 2 dijkstra只是找一条路径打印，就算是现场实现这个打印一条最短路径算法的代码也是
不简单的，A家啥时候这么难了 |
H****r
发帖数: 2801 | 3 啥叫”所有最短路径“？
【在 h****a 的大作中提到】
: 给一个无向图找出给定起始点到给定结束点的所有最短路径并打印
|
A**u
发帖数: 2458 | 4 靠。。。竟然搞这种
【在 h****a 的大作中提到】
: 给一个无向图找出给定起始点到给定结束点的所有最短路径并打印
|
f*********y
发帖数: 376 | 5 the shortest part may not be unique
【在 H****r 的大作中提到】
: 啥叫”所有最短路径“？
|
d**********x
发帖数: 4083 | 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**********x
发帖数: 4083 | 7 这个真心不难
O(n^3)的all pair最短路径一共不过5行，加上上面这个dfs打印最短路径的程序也就10
分钟
也许这故事说明算法导论还是要读读的，光靠背面试题吧。。
【在 w****x 的大作中提到】
: dijkstra只是找一条路径打印，就算是现场实现这个打印一条最短路径算法的代码也是
: 不简单的，A家啥时候这么难了
|
C***U
发帖数: 2406 | 8 clrs里面的一章吧。。。
【在 h****a 的大作中提到】
: 给一个无向图找出给定起始点到给定结束点的所有最短路径并打印
|
o****n
发帖数: 349 | 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****r
发帖数: 2801 | 10 devilphoenix 太牛
10
【在 d**********x 的大作中提到】
: 这个真心不难
: O(n^3)的all pair最短路径一共不过5行，加上上面这个dfs打印最短路径的程序也就10
: 分钟
: 也许这故事说明算法导论还是要读读的，光靠背面试题吧。。
|
|
|
H****r
发帖数: 2801 | 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**********x
发帖数: 4083 | 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
: 也是
|
w****x
发帖数: 2483 | 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**********x
发帖数: 4083 | 14 任意两点的距离可以用Floyd-Marshall得到，O(n^3)
或者用Dijkstra求单源最短路径，O(n^2)。
离之
【在 w****x 的大作中提到】
:
: 好像不能假定任何两点之间的距离都知道吧，没直接连上怎么办？
: 没记录遍历过的点。程序有跑过吗？
|
H****r
发帖数: 2801 | 15 对啊，这graph是咋表示的？要是点对点矩阵的话任意两点间距离还是有的， 不相连的
话是Infinity...
【在 w****x 的大作中提到】
:
: 好像不能假定任何两点之间的距离都知道吧，没直接连上怎么办？
: 没记录遍历过的点。程序有跑过吗？
|
d**********x
发帖数: 4083 | 16 Floyd Marshall里面是先构建一矩阵，无穷标记为-1
然后逐个update，直到取到所有最短距离
and make
【在 H****r 的大作中提到】
: 对啊，这graph是咋表示的？要是点对点矩阵的话任意两点间距离还是有的， 不相连的
: 话是Infinity...
|
h****t
发帖数: 184 | 17 这个用 BFS 遍历图不就可以吗？
【在 h****a 的大作中提到】
: 给一个无向图找出给定起始点到给定结束点的所有最短路径并打印
|
d**********x
发帖数: 4083 | 18 仔细想想。。？
【在 h****t 的大作中提到】
: 这个用 BFS 遍历图不就可以吗？
|
h****t
发帖数: 184 | 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; j
PrintAllPath(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 的大作中提到】
: 仔细想想。。？
|
