Edward Moore's Algorithm is an improvement over Bellman-Ford's algorithm and can compute single-source shortest paths in weighted (including negative weights) directed graphs. It has an average running time of O(|E|) on random graphs and the same worst-case complexity as Bellman-Ford's algorithm of O(|V| x |E|).

Boost::Breadth First Search is the implementation of the classic Breadth First Algorithm in the Boost Graph Library. It is a basic graph traversal algorithm which can be applied to any type of graph. One of its various applications is to find the path with minimum edges from a given source to an arbitrary destination. It has a linear time complexity of O(|V| + |E|).

Binary Breadth First Search is a modification of the standard Breadth First Search algorithm and can calculate single-source shortest paths in a weighted graph where weights of all edges are either zero or some constant C. It has a linear time complexity of O(|V| + |E|) compared to O(|E| + |V| log |V|) of Dijkstra’s algorithm.

I propose to add the above three algorithms to pgRouting during the GSoC period.

Organization

Student

Gudesa Venkata Sai Akhil

Mentors

  • Sourabh Garg
  • Cayetano Benavent
close

2019