giraph-user mailing list archives

Site index · List index
Message view « Date » · « Thread »
Top « Date » · « Thread »
From Sebastian Schelter <>
Subject Re: All pairs shortest paths
Date Mon, 24 Sep 2012 19:55:21 GMT
Hi Venkata,

The result of All-Pairs-Shortest-Paths is quadratic in the number of
vertices which makes it infeasible for sufficiently large graphs.


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.

View raw message