Re: Multiple sources shortest path

[Sebastian]

In general, all-pairs-shortest-paths is a non-scalable problem as it 
produces output proportional to the square of the number of vertices in 
a network.

--sebastian

On 15.02.2015 12:37, Vasiliki Kalavri wrote:
Hi,

you can certainly use a for-loop like this to run SSSP several times.
Just make sure you return or store the result of the computation for
each source, by adding a data sink e.g.:

for (id : Ids) {
           graph.run(new SingleSourceShortestPaths<Long>(id, maxIterations))
.getVertices().print();
}

However, if you have a large amount of source nodes, executing one SSSP
for each of them is probably not the most efficient way to go.
Instead, you could maybe write a custom multiple shortest paths program,
where each node calculates distances for multiple sources in each
iteration. In this case, the vertex value could be a vector of size
equal to the number of input sources.

Cheers,
V.

On 14 February 2015 at 12:26, HungChang <unicorn.bana...@gmail.com
<mailto:unicorn.bana...@gmail.com>> wrote:

    Hi,

    In graph api there's an single source shortest path library.

    DataSet<Vertex&lt;Long,Double>> singleSourceShortestPaths =
                     graph.run(new
    SingleSourceShortestPaths<Long>(srcVertexId,
    maxIterations)).getVertices();

    For Multiple Source, would it be possible to run it for all nodes using
    for-loop?
    for example,

    for(Node node: nodes){
      DataSet<Vertex&lt;Long,Double>> singleSourceShortestPaths =
                     graph.run(new SingleSourceShortestPaths<Long>(node,
    maxIterations)).getVertices();
    }




    --
    View this message in context:
    
http://apache-flink-incubator-user-mailing-list-archive.2336050.n4.nabble.com/Multiple-sources-shortest-path-tp729.html
    Sent from the Apache Flink (Incubator) User Mailing List archive.
    mailing list archive at Nabble.com.