B*******1
发帖数: 2454 | 1 Main Question:
Design a parallel Breadth First Search algorithm for a directed weighted
graph.
Basically you need to find the minimum cost to reach to a node from the
starting node . (Just save the optimum cost and not the optimum path)
. Calculate and output the optimum reachability cost for all the nodes from
a given starting point.
Implement in C with openMP.
1. How about using DFS or Shortest path first instead. Would these
algorithms perform better than BFS with parallel implementation. Yes/No Why?
怎么并行最好啊？ |
r*******g
发帖数: 1335 | |
B*******1
发帖数: 2454 | 3 careercup说了不行了，bfs对weighted graph不行啊。 |
y*******g
发帖数: 6599 | 4 bfs和weight 没关系吧。
dijkstra之类的priority first search才和weight有关系
【在 B*******1 的大作中提到】
: careercup说了不行了，bfs对weighted graph不行啊。
|
B*******1
发帖数: 2454 | 5 但是现在有weight，还可以用bfs找minimum cost？
如果是的话，是不是要遍历所有路径，而不是一到达target，就退出？ 因为cost可能不是最小的。
【在 y*******g 的大作中提到】
: bfs和weight 没关系吧。
: dijkstra之类的priority first search才和weight有关系
|
y*******g
发帖数: 6599 | 6 嗯，要遍历所有路径。
能不是最小的。
【在 B*******1 的大作中提到】
: 但是现在有weight，还可以用bfs找minimum cost？
: 如果是的话，是不是要遍历所有路径，而不是一到达target，就退出？ 因为cost可能不是最小的。
|
B*******1
发帖数: 2454 | 7 thanks.
【在 y*******g 的大作中提到】
: 嗯，要遍历所有路径。
:
: 能不是最小的。
|
y*******g
发帖数: 6599 | 8 其实我觉得Floyd–Warshall 并行应该没问题吧？
【在 B*******1 的大作中提到】
: thanks.
|
B*******1
发帖数: 2454 | 9 那样子的话那个matrix被多个CPU共享和update，似乎会更加慢，刚有人才说了cache的
问题。 |
