1 of 4

SHORTEST PATH ALGORITHMS

​

​

​

​

​

GSoC 2018

Sourabh Garg

IIT (BHU), India

2 of 4

pgr_bellmanFord

​

​

0

​

​

Explanation Code

​

START

0

7 6 5

​

2

START

END

8

1 2 END

agg_cost(5)= 11

3 of 4

pgr_dagShortestPath

3

Explanation Code

START

4

0(0) 1(3) 3(7) agg_cost(3) = 7

3

4 of 4

Experimentation: Parallel Dijkstra

  • Distributed Graph(vertices and edges) among processors.
  • Apply dijkstra’s algorithm over distributed graph

Explanation[1] [2]

4

Fig. Distributed Graph with

Two processors & 7 nodes

Code