Contributor
Abhinav_Jain

Implement pgr_withPointsKSP and Add Overloads


Mentors
Ashish-Kumar, Vicky Vergara
Organization
OSGeo (Open Source Geospatial Foundation)
Technologies
postgresql, c++, gis, Graph Theory
Topics
c++, software development, Graph Theory, dijkstra
The project aims to implement pgr_withPointsKSP and all its overloads. Yen's algorithm computes single-source K-shortest loopless paths for a graph with non-negative edge cost. It employs any shortest path algorithm to find the best path, then proceeds to find K − 1 deviations of the best path. Sometimes the applications work “on the fly” starting from a location that is not a vertex in the graph. Those locations, in pgRouting, are called points of interest. So this function will modify the graph to include these points of interest and, using Yen’s Algorithm finds K shortest paths.