Graph Algorithms like Dijkstra’s single source shortest path algorithm are widely applied in many routing applications, but for the Large-scale graph, computation problem may arise. It may be beneficial to exploit the high-performance parallel computing system, by implementing distributed graph algorithms in pgRouting.The current state of the pgRouting doesn’t support any parallel algorithm. I am proposing to add Parallel Dijkstra’s Algorithm using Parallel BGL functionalities and additionally a classical sequential graph algorithm namely, bellman_ford_shortest_paths to pgRouting during this GSoC period.

Organization

Student

Sourabh Garg

Mentors

  • cvvergara
  • Daniel Kastl
close

2018