mudit.f2004912
BAN USER- 0of 0 votes
AnswersMain Question:
- mudit.f2004912 in United States
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 <given>. (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?| Report Duplicate | Flag | PURGE
Google Software Engineer / Developer Distributed Computing
Yes, I believe everyone knows how to implement BFS, DFS or shortest path. But the point is how can we optimize it by performing mutually exclusive parallel computations on different nodes and yet get the right results at the end.
May be to split the graph and work on them parallely.
Thanks Divya,
- mudit.f2004912 October 20, 2011Well a good implementation. However, how do we do it for weighted graph. I have an idea, why not do a topological sorting on nodes and then apply BFS as to the trick is, only add a node to the queue when it has exhausted all it's incoming edges, that means all the parents have already been calculated for the minimum distance.