APSP

This page is a draft for the implementation of All Pairs Shortest Path Problem in pgRouting.

Basic Idea

Notations: m - edges. n - vertices. v - vertices in subset.

As the map is a planar graph, number of edges m = O(n). In that case, the dijextra Shortest path algorithm will take O(m + n log n) that is O(n logn) time. Now, if we want to find APSP between small subset of vertices v, we can call dijextra v^2 times to get total complexity O(v^2* n log n). We will have a good bound until (v^2 log n) < n^2. This will also return the paths between vertices.

When (v^2 log n) > n^2 we can use Warshall algo. We can simultaneously create a n^2 path matrix along with the distance matrix and use that to extract paths. Pseudo code is present here: http://en.wikipedia.org/wiki/Floyd%E2%80%93Warshall_algorithm. The paths can be extracted again in O(n^3) time as it takes O(n) time to extract one path. The boost implementation of Warshall returns just a distance matrix: http://www.boost.org/doc/libs/1_45_0/libs/graph/doc/floyd_warshall_shortest.html

Possible pseudo-code Build graph from bounding box if num pairs is < some limit then //According to bound mentioned above loop thought pairs and solve shortest path else use APSP algorithm return results as: from,to,distance[,array{from,node,node,...,to}]

**Possible function prototype **

CREATE OR REPLACE FUNCTION apsp( sql text, n_ids text, m_ids text, directed boolean, has_reverse_cost boolean) RETURNS SETOF <???>

With sql as ...

SELECT id, source, target, cost FROM edge_table

... like for Dijkstra, and n_ids/m_ids as ...

SELECT id FROM edge_table

to select the relevant points for the n-m distance matrix.

Results that should be returned Since, we mostly need a distance matrix, there should be at least an option to return distance matrix only and omit extra work on extracting paths. Should it be different function? It would be nice if extracted paths could be in form of phRouting 'path' type with additional 'from' and 'to' columns.

Points that need discussion

Results that should be returned Since, we mostly need a distance matrix, there should be at least an option to return distance matrix only and omit extra work on extracting paths. Should it be different function? It would be nice if extracted paths could be in form of phRouting 'path' type with additional 'from' and 'to' columns.

Points that need discussion

• What should be exact Function arguments?

• What should the Pseudo Code look like?

• What should be exact Function arguments?

• What should the Pseudo Code look like?

• Should we use boost Warshall Implementation or write it from scratch so as to build simultaneous path Matrix?

• What should be functions return format?

• How can we provide options for n source, to m destination kind of problem?