Hi Venkata, The result of All-Pairs-Shortest-Paths is quadratic in the number of vertices which makes it infeasible for sufficiently large graphs.
Best, Sebastian On 24.09.2012 20:24, Venkata Sastry Malladi wrote: > I'm thinking of modifying the simple shortest paths algorithm so that it > calculates the shortest paths between all pairs of nodes (not just from a > single source node). I wanted to get some general advice on whether these > are feasible in Giraph: > > 1. Without quitting the job after all vertices voteToHalt(), is it possible > to just restart from superstep 0, but with a different source node? In > other words, when we want to do simultaneous runs of the simple shortest > paths algorithm, how can we avoid the overhead of re-reading the graph into > memory between the runs? > > 2. Is it possible to run some kind of reducer before the vertices are > written to the output? Let's say the VertexWriter outputs something like > (Source, Destination) -> Route for each node. Is it possible to combine > many such outputs to produce a single output? Like (Source, Destination) - >> (Route1, Route2, Route3). > > Thanks, > Venkat. >
