incubator-hama-commits mailing list archives

Site index · List index
Message view « Date » · « Thread »
Top « Date » · « Thread »
From Apache Wiki <wikidi...@apache.org>
Subject [Hama Wiki] Update of "SSSP" by praveen sripati
Date Thu, 19 Apr 2012 10:48:48 GMT
Dear Wiki user,

You have subscribed to a wiki page or wiki category on "Hama Wiki" for change notification.

The "SSSP" page has been changed by praveen sripati:
http://wiki.apache.org/hama/SSSP?action=diff&rev1=9&rev2=10

   * The SSSP (abbr. for Single Source Shortest Paths) algorithm described in the Google Pregel
paper was used.
   * Introduces IO usage, partitioning based on hashing of vertextID, and collective communication.
  
+ == Short summary of the algorithm ==
+ 
+  * Initialize all vertices' cost to reach it to INFINITY, just the start vertex will have
cost 0.
+ 
+  * Initially send the new cost to all adjacent vertex containing the new cost plus the edge
weight between them
+ 
+  * Reviewing messages: if the cost coming from a message is lower than the actual cost,
update the cost and send a message to the adjacent vertices, containing the new cost plus
the edge weight between them (similar to the last step)
+ 
+  * Repeat the last step until no updates can be made anymore.
  
  == Usage ==
  
@@ -21, +30 @@

  The file that Hama can successfully parse is a TextFile that has the following layout:
  
  {{{
- Berlin	Frankfurt:20	Munich:50
+ Berlin\tFrankfurt:20\tMunich:50
- Frankfurt	Berlin:20	Munich:10
+ Frankfurt\tBerlin:20\tMunich:10
  Munich
  }}}
  

Mime
View raw message