Hello all,
I am Sourabh Garg, and This is my final report for my GSoC project.
Title: Implement Parallel Dijkstra’s and BellmanFord algorithm by the Boost Graph Library.
Organization: PgRouting under OSGeo
Abstract:
Graph Algorithms like Dijkstra’s single source shortest path algorithm is widely applied in many routing applications, but it is constrained by nonnegative edge’s weight and is more efficient to use DAG shortest path algorithm(topological sort) in case of Directed Acyclic Graph.
Finding the shortest path from a source vertex to target using the bellmanford algorithm for Graphs with negative weighted edges and dag_shortest_path algorithm for the Directed acyclic graph are major
deliverables.
Often such algorithms are applied over Largescale graphs, where computation problem may arise. It may be beneficial to exploit the highperformance parallel computing system, by implementing distributed graph algorithms in pgRouting. I have developed the testing base for parallel Boost Graph algorithm.
Implemented functions
:
 pgr_bellmanFord()  Returns the shortest path for the graph with negative weighted edges.
 pgr_dagShortestPath()  Returns the shortest path for the Directed Acyclic Graph.
State of the art before the project: pgRouting didn’t have above functionalities before my GSoC.
Addition that my project brought to pgRouting:
```
The deliverables are code, full documentation, documentation tests, pgTap of above functions.
```
**Pending Work:** I have done experimentation with boost parallel graph library to generate distributed graph and apply dijkstra's algorithm over it. It was quite challenging to integrate the parallel version of algorithms with pgRouting architecture.
Future Directions:

Implement full functionality of parallel Dijkstra in pgrouting architecture.

Implement the feature to include the negative weighted edges in pgRouting graphs.
Links:

Wiki: https://github.com/pgRouting/pgrouting/wiki/GSoC2018ParallelDijkstraandBellmanFord

Last Pull Request: https://github.com/pgRouting/pgrouting/pull/1082

Slide: https://docs.google.com/presentation/d/1ESngDemJKLmvWCO6uisd1bmhXGYdjc5ERaZEWdqOx0/edit?usp=sharing

Tag: https://github.com/pgRouting/pgrouting/releases/tag/gsoc2018codeSGlw
Best Regards,
Sourabh Garg